\(A\ Regular\ Triangle\)

咕咕

\(B\ Red\ or\ Blue\)

咕咕咕

\(C\ Snuke\ the\ Wizard\)

我可能脑子真的坏掉了……

容易发现不管怎么移动相对顺序都是不变的，那么我们二分找到最右边的会从左边掉出去的点，它左边所有点也会从左边掉出去，最左边的会从右边掉出去的点同理

//minamoto#include
    
     #define R register#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}int read(char *s){    R int len=0;R char ch;while(((ch=getc())>'Z'||ch<'A'));    for(s[++len]=ch;(ch=getc())>='A'&&ch<='Z';s[++len]=ch);    return s[len+1]='\0',len;}inline char getop(){R char ch;while((ch=getc())>'Z'||ch<'A');return ch;}const int N=2e5+5;struct node{char c,d;}q[N];char s[N];int n,m,l,r,mid,ansl,ansr;bool ck(int pos){    int x=mid;    fp(i,1,m)if(s[x]==q[i].c){        q[i].d=='L'?--x:++x;        if(x<1||x>n)return x==pos;    }    return false;}int main(){//  freopen("testdata.in","r",stdin);    n=read(),m=read(),read(s);    fp(i,1,m)q[i].c=getop(),q[i].d=getop();    l=1,r=n,ansl=0;    while(l<=r){        mid=(l+r)>>1;        ck(0)?(ansl=mid,l=mid+1):r=mid-1;    }    l=1,r=n,ansr=n+1;    while(l<=r){        mid=(l+r)>>1;        ck(n+1)?(ansr=mid,r=mid-1):l=mid+1;    }    printf("%d\n",ansr-ansl-1);    return 0;}
     
    

\(D\ Modulo\ Operations\)

冷静下来突然发现……它题目中说的\(set\)莫不是就是指\(c++\)意义上的\(set\)？不会有重复元素？

如果先对一个小的数取模再对一个大的数取模，那么后面那个大的数显然没有什么卵用，所以有用的肯定是一个递减序列

一个数有用，当且仅当所有比它小的数都在它后面，我们设它的排名为\(i\)，那么它以及所有比它小的数的排列个数为\(i!\)，它排在最前面的有\((i-1)!\)，所以它有用的概率就是\({1\over i}\)

那么我们先从小到大\(sort\)一下，然后倒着做

记\(p_{i,j}\)表示满足所有有用的数字为\([i,n]\)的一个子序列，且最后余数为\(j\)的概率，初值为\(p_{n+1,x}=1\)

转移的话，先给柿子

\[f_{i,j\bmod a_i}+=f_{i+1,j}\times {1\over i}\]

\[f_{i,j}+=f_{i+1,j}\times \left({1-{1\over i}}\right)\]

上面的柿子的意思就是，如果当前这个数有用，那么就是上面的转移，没用的话就是下面的转移

那么最后\(f_{1,j}\times n!\)就是余数为\(j\)的期望排列个数

//minamoto#include
    
     #define R register#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}const int N=205,M=1e5+5,P=1e9+7;inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}int ksm(R int x,R int y){    R int res=1;    for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;    return res;}int inv[N],p[N][M],a[N],id[N];int n,x,fac,res;int main(){//  freopen("testdata.in","r",stdin);    n=read(),x=read(),fac=1;    fp(i,1,n)a[i]=read(),fac=mul(fac,i);    sort(a+1,a+1+n);    inv[0]=inv[1]=1;fp(i,2,n)inv[i]=mul(P-P/i,inv[P%i]);    p[n+1][x]=1;    fd(i,n,1)fp(j,0,x)        p[i][j%a[i]]=add(p[i][j%a[i]],mul(p[i+1][j],inv[i])),        p[i][j]=add(p[i][j],mul(p[i+1][j],P+1-inv[i]));    fp(i,1,x-1)res=add(res,mul(p[1][i],i));    printf("%d\n",mul(res,fac));    return 0;}
     
    

\(E\ Black\ or\ White\)

完了我连这种题都做不来了……

我们记\(p_i\)表示\(i\)次取完黑巧克力的答案，\(q_i\)表示\(i\)次取完白巧克力的答案，那么第\(i\)次的答案就是

\[{1-p_{i-1}-q_{i-1}\over 2}+q_{i-1}\]

即如果前\(i-1\)次哪种巧克力都没有取完，概率就要乘上\({1\over 2}\)，如果白巧克力已经取完，那么概率就是\(1\)

\(p_i\)和\(q_i\)可以直接递推了

//minamoto#include
    
     #define R register#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)using namespace std;char sr[1<<21],z[20];int K=-1,Z=0;inline void Ot(){fwrite(sr,1,K+1,stdout),K=-1;}void print(R int x){    if(K>1<<20)Ot();if(x<0)sr[++K]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++K]=z[Z],--Z);sr[++K]='\n';}const int N=2e5+5,P=1e9+7,inv2=500000004;inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}int ksm(R int x,R int y){    R int res=1;    for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;    return res;}int fac[N],ifac[N],bin[N],pw[N],pb[N],b,w;inline int C(R int n,R int m){return m>n?0:1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;}int main(){//  freopen("testdata.in","r",stdin);    scanf("%d%d",&b,&w);    fac[0]=ifac[0]=1;fp(i,1,b+w)fac[i]=mul(fac[i-1],i);    ifac[b+w]=ksm(fac[b+w],P-2);fd(i,b+w-1,1)ifac[i]=mul(ifac[i+1],i+1);    bin[0]=1;fp(i,1,b+w)bin[i]=mul(bin[i-1],inv2);    fp(i,1,b+w){        pw[i]=add(pw[i-1],mul(C(i-1,w-1),bin[i]));        pb[i]=add(pb[i-1],mul(C(i-1,b-1),bin[i]));        print(add(1ll*(1+P-pw[i-1]+P-pb[i-1])*inv2%P,pw[i-1]));    }    return Ot(),0;}
     
    

\(F\ More\ Realistic\ Manhattan\ Distance\)

我们把起点和终点周围所有方向的边各找出来一条，这样最多是一个\(6\times 6\)的网格图，直接跑最短路

代码已经是完全照抄\(yyb\)巨巨的了

//minamoto#include
    
     #define R register#define ll long long#define inf 0x3f3f3f3f#define fp(i,a,b) for(R int i=(a),I=(b)+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;char buf[1<<21],*p1=buf,*p2=buf;inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}int read(){    R int res,f=1;R char ch;    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');    return res*f;}int read(char *s){    R int len=0;R char ch;while(((ch=getc())>'Z'||ch<'A'));    for(s[++len]=ch;(ch=getc())>='A'&&ch<='Z';s[++len]=ch);    return s[len+1]='\0',len;}char sr[1<<21],z[20];int C=-1,Z=0;inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}void print(R int x){    if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x;    while(z[++Z]=x%10+48,x/=10);    while(sr[++C]=z[Z],--Z);sr[++C]='\n';}vector
       
        N,S,W,E;int Pre(vector
        
          &A,int x){    if(A.empty())return 1;    int l=0,r=A.size()-1,res=0;    while(l<=r){        int mid=(l+r)>>1;        A[mid]<=x?(res=mid,l=mid+1):r=mid-1;    }    return A[res];}int suf(vector
         
           &A,int x){ if(A.empty())return 1; int l=0,r=A.size()-1,res=r; while(l<=r){ int mid=(l+r)>>1; A[mid]>=x?(res=mid,r=mid-1):l=mid+1; } return A[res];}struct eg{int v,nx,w;}e[1005];int head[105],tot;inline void add(R int u,R int v,R int w){e[++tot]={v,head[u],w},head[u]=tot;}char s[100005],t[100005];int n,m,Q,cnt,id[25][25],dis[205],vis[205];struct node{ int u,d; node(){} node(R int uu,R int dd):u(uu),d(dd){} inline bool operator <(const node &b)const{return d>b.d;}};priority_queue
          
           q;int spfa(int S,int T){ fp(i,1,cnt)dis[i]=inf,vis[i]=0; q.push(node(S,0)),dis[S]=0; while(!q.empty()){ int u=q.top().u;q.pop();if(vis[u])continue;vis[u]=1; go(u)if(cmin(dis[v],dis[u]+e[i].w))q.push(node(v,dis[v])); } return dis[T]