记录每一次操作的玩家为操作序列（去掉第一次），需要满足：$a$的个数为$n$且以$a$为结尾，$b$和$c$的个数分别不超过$m$和$k$
其所对应的概率：每一个字符恰好确定一张卡牌，因此即$3^{n+m+k-|s|}$
暴力枚举$b$和$c$的个数，即$\sum_{i=0}^{m}\sum_{j=0}^{k}{n+i+j-1\choose i}{n+j-1\choose j}3^{m+k-i-j}$
将组合数用阶乘展开，即$\sum_{i=0}^{m}\sum_{j=0}^{k}\frac{(n+i+j-1)!3^{m+k-i-j}}{(n-1)!i!j!}$
枚举$i+j=s$，即$\frac{\sum_{s=0}^{m+k}(n+s-1)!3^{m+k-s}\sum_{0\le i\le m,0\le s-i\le k}\frac{1}{i!(s-i)!}}{(n-1)!}$
关于后者显然是一个多项式乘法的形式，但由于模数是$10^{9}+7$，需要写一个拆系数fft/三模数ntt，复杂度为$o(n\log n)$且常数较大
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 300005
4 #define M (1<<20)
5 #define mod 1000000007
6 #define K 40000
7 #define cd complex<double>
8 #define PI acos(-1.0)
9 int n,m,k,ans,fac[M],inv[N],mi[M],rev[M];
10 cd a1[M],a2[M],b1[M],b2[M],c1[M],c2[M],c3[M],w[M];
11 void fft(cd *a,int p){
12 for(int i=0;i<M;i++)
13 if (i<rev[i])swap(a[i],a[rev[i]]);
14 for(int i=2;i<=M;i<<=1)
15 for(int j=0;j<M;j+=i)
16 for(int k=0;k<(i>>1);k++){
17 cd s=w[(i>>1)+k];
18 if (p)s=conj(s);
19 cd x=a[j+k],y=a[j+k+(i>>1)]*s;
20 a[j+k]=x+y;
21 a[j+k+(i>>1)]=x-y;
22 }
23 if (p){
24 for(int i=0;i<M;i++)a[i]/=M;
25 }
26 }
27 int main(){
28 fac[0]=inv[0]=inv[1]=mi[0]=1;
29 for(int i=1;i<M;i++)fac[i]=1LL*fac[i-1]*i%mod;
30 for(int i=2;i<N;i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
31 for(int i=2;i<N;i++)inv[i]=1LL*inv[i-1]*inv[i]%mod;
32 for(int i=1;i<M;i++)mi[i]=3LL*mi[i-1]%mod;
33 scanf("%d%d%d",&n,&m,&k);
34 for(int i=0;i<M;i++)rev[i]=(rev[i>>1]>>1)+((i&1)*(M>>1));
35 for(int i=1;i<M;i<<=1)
36 for(int j=0;j<i;j++)w[i+j]=cd(cos(j*PI/i),sin(j*PI/i));
37 for(int i=0;i<=m;i++)a1[i]=cd(inv[i]/K,0);
38 for(int i=0;i<=m;i++)a2[i]=cd(inv[i]%K,0);
39 for(int i=0;i<=k;i++)b1[i]=cd(inv[i]/K,0);
40 for(int i=0;i<=k;i++)b2[i]=cd(inv[i]%K,0);
41 fft(a1,0);
42 fft(a2,0);
43 fft(b1,0);
44 fft(b2,0);
45 for(int i=0;i<M;i++){
46 c1[i]=a1[i]*b1[i];
47 c2[i]=a1[i]*b2[i]+a2[i]*b1[i];
48 c3[i]=a2[i]*b2[i];
49 }
50 fft(c1,1);
51 fft(c2,1);
52 fft(c3,1);
53 for(int i=0;i<=m+k;i++){
54 int s1=llround(c1[i].real())%mod;
55 int s2=llround(c2[i].real())%mod;
56 int s3=llround(c3[i].real())%mod;
57 int s=(1LL*K*K%mod*s1+1LL*K*s2+s3)%mod;
58 ans=(ans+1LL*fac[n+i-1]*mi[m+k-i]%mod*s)%mod;
59 }
60 ans=1LL*ans*inv[n-1]%mod;
61 printf("%d",ans);
62 }
View Code
事实上还有更好的做法，由于$\frac{1}{i!(s-i)!}=\frac{{s\choose i}}{s!}$，代入即$\frac{\sum_{s=0}^{m+k}s!(n+s-1)!3^{m+k-s}\sum_{0\le i\le m,0\le s-i\le k}{s\choose i}}{(n-1)!}$
考虑后者，也就是$\sum_{i=l}^{r}{s\choose i}$，定义为$f(s,l,r)$，我们将这一行的每一个数乘以2（即有2个），在将非首尾的数利用杨辉三角合并，即$2f(s,l,r)=f(s,l+1,r)+{s\choose l}+{s\choose r}$
利用这个式子，注意到每一次$s$增加区间两端点变化为为$o(1)$，就可以线性的完成，复杂度为$o(n)$
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 1000005
4 #define mod 1000000007
5 int n,m,k,ans,fac[N],inv[N],mi[N];
6 int c(int n,int m){
7 if (n<m)return 0;
8 return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;
9 }
10 int main(){
11 fac[0]=inv[0]=inv[1]=mi[0]=1;
12 for(int i=1;i<N;i++)fac[i]=1LL*fac[i-1]*i%mod;
13 for(int i=2;i<N;i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;
14 for(int i=2;i<N;i++)inv[i]=1LL*inv[i-1]*inv[i]%mod;
15 for(int i=1;i<N;i++)mi[i]=3LL*mi[i-1]%mod;
16 scanf("%d%d%d",&n,&m,&k);
17 //l=max(s-k,0),r=min(m,s)
18 int s=1,l=0,r=0;
19 for(int i=0;i<=m+k;i++){
20 if (i){
21 s=((2*s%mod+mod-c(i-1,l))%mod+mod-c(i-1,r))%mod;
22 l++;
23 while (max(i-k,0)<l)s=(s+c(i,--l))%mod;
24 while (l<max(i-k,0))s=(s+c(i,l++))%mod;
25 while (r<min(m,i))s=(s+c(i,++r))%mod;
26 while (min(m,i)<r)s=(s+c(i,r--))%mod;
27 }
28 ans=(ans+1LL*fac[n+i-1]*mi[m+k-i]%mod*s%mod*inv[i])%mod;
29 }
30 ans=1LL*ans*inv[n-1]%mod;
31 printf("%d",ans);
32 }
View Code