考这场考试不如补觉。
怀疑组题人（都不算是出题人）就是从网上随便摘了三道题揉巴揉巴题解也懒得写了就直接丢上来了。
连部分分都瞎出完了就
$4.5$小时。面对两个视频课原题但是根本没法写。然后面对出题人口胡根本没讲
做这套题就纯当看了下$IOI$的新闻。。。。
T1：拿钱了
暂时无解。
T2：打铁了
不会。去看牛的博客。
$dy$讲的原题，他讲的暴力是对的，剩下乱糟糟的。
发$std$了而且牛神$AC$了，有空再问吧。
T3：梦里啥都有
原题《青春猪头少年不会梦到兔女郎学姐》。数据范围削弱$n \le 50,a_i \le 100$
没时间写了。。
https://www.luogu.com.cn/blog/user13052/solution-p6151
然而这篇博客有些地方写的不是很好。
首先是关于所有方案除$j$再乘$m$。这是对的但是他解释的有问题。
考虑到有些方案中是有循环节的，再这时候不能单纯考虑被计算了几次而直接除再乘，因为直接乘会出现同构的串。
一种正确的理解方式是：对于一个已知串，它本应该被计算的次数是 循环节长度 次。
然而事实上直接做的话统计到的次数是第一段长度乘以循环节个数除以总长度。所以才需要一乘一除。
另一方面它说的不好的一点是，具体实现过程中，并不需要用一端的减去两端的。
具体而言这么考虑，对于一种首长度为$4$尾长度为$3$的方案，为什么不用再刻意减掉它？
因为你做长度为$7$的首端的时候带上了容斥系数把对应的干掉了，同时你还乘了$m$做轮换，所以$4-3$这种轮换也是被容斥掉了。
时间复杂度和代码倒好说。。。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define S 10001 4 #define mod 1000000007 5 int n,r[S],tot,fac[S],inv[S],F[55][105],dp[S],R[S]; 6 int qp(int b,int t,int a=1){for(;t;t>>=1,b=1ll*b*b%mod)if(t&1)a=1ll*a*b%mod;return a;} 7 int C(int b,int t){return t>b||t<0?0:fac[b]*1ll*inv[t]%mod*inv[b-t]%mod;} 8 int cal(int _){ 9 for(int i=_;i<=r[1];++i)dp[i]=1ll*F[1][i]*inv[i-_]%mod*inv[i]%mod*fac[i-1]%mod; 10 int len=r[1]; 11 for(int i=2;i<=n;++i){ 12 for(int j=1;j<=len;++j)for(int k=1;k<=r[i];++k)R[j+k]=(R[j+k]+1ll*dp[j]*F[i][k]%mod*inv[k])%mod; 13 len+=r[i]; 14 for(int j=1;j<=len;++j)dp[j]=R[j],R[j]=0; 15 }int ans=0; 16 for(int i=_;i<=len;++i)ans=(ans+1ll*dp[i]*fac[i-_])%mod; 17 return ans*1ll*tot%mod; 18 } 19 int main(){ 20 cin>>n; for(int i=1;i<=n;++i)cin>>r[i],tot+=r[i]; 21 for(int i=fac[0]=1;i<S;++i)fac[i]=fac[i-1]*1ll*i%mod; 22 inv[S-1]=qp(fac[S-1],mod-2); 23 for(int i=S-2;~i;--i)inv[i]=inv[i+1]*(i+1ll)%mod; 24 for(int i=1;i<=n;++i)for(int j=1;j<=r[i];++j)for(int a=j;a<=r[i];++a) 25 F[i][j]=(F[i][j]+1ll*C(r[i]+a-1,a+a-1)*(a-j&1?mod-1:1)%mod*C(a-1,j-1))%mod; 26 cout<<cal(1)<<endl; 27 }
原文：https://www.cnblogs.com/hzoi-DeepinC/p/12790680.html
