[atAGC056E]Cheese
对每一个$k$分别计算答案,通过旋转不妨仅考虑$k=n-1$时
记$a_{i}$为第$i$次扔奶酪的位置,$x$为经过$n-0.1$的奶酪次数(允许重复)
记$b_{i}$为经过$i+0.1$的奶酪次数,则有$b_{i}=x+\sum_{j=1}^{n-1}[a_{j}\le i]-i$(总共$x+\sum_{j=1}^{n-1}[a_{j}\le i]$,再去掉被前$i$个老鼠吃掉的),并且其之后都会经过第$i$只老鼠
考虑对应的概率,对$i$分类讨论:
1.若$i=n-1$,即这些奶酪都不能吃,概率也即$\frac{1}{2^{b_{n-1}}}$(显然$b_{n-1}\ge 0$)
2.若$i\ne n-1$,枚举其"吃掉的时间"(即第几次经过时),概率也即$\sum_{j=1}^{b_{i}}\frac{1}{2^{j}}=\begin{cases}1-\frac{1}{2^{b_{i}}}&(b_{i}\ge 0)\\0&(b_{i}<0)\end{cases}$
同时,确定"吃掉的时间"后,考虑构造对应方案,具体方式如下——
记$pos_{i}$为第$i$只老鼠"吃掉的时间"(编号为$[1,b_{i}]$),设此时$pos_{t}=\min pos_{i}$(若有多个取$a_{i}$顺时针旋转第一个$t$),令该奶酪经过$t+0.1$共$pos_{t}$次后被第$t$只老鼠吃掉,并将所有$pos_{j}$减去$j+0.1$被经过的次数
关于两者的对应性,考虑以下性质:
1.构造的方案合理(会发生),即$a_{i}\in [0,n),x\ge 0$且任意时刻$pos_{i}\in Z^{+}$,后者根据$t$的构造显然
2.构造的方案符合所给限制,"吃掉的时间"显然相同,但经过$n-0.1$的次数并不一定为$x$
从一组方案的角度考虑,其不仅对本身的$x=x_{0}$有贡献,还会对所有$x\ge x_{0}$有贡献,同时这仅会影响$b_{n-1}$(对于之前已经确定"吃掉的时间"),也即乘上$\frac{1}{2}$,进而$\sum_{x\ge 0}\frac{1}{2^{x}}=2$
3.每一组方案均对应于唯一的信息(限制,即$a_{i},x$和"吃掉的时间"),显然成立
综合上述三点,即可得到对应性,且根据第2点还要将上述概率再乘上$\frac{1}{2}$
另一方面,若存在$b_{i}<0$根据$b_{0}=x\ge 0,b_{i}\le b_{i+1}+1$总还存在$b_{j}=0$,因此不妨令其仍为$1-\frac{1}{2^{b_{i}}}$
换言之,最终对答案的贡献即$\frac{1}{2^{b_{n-1}+1}}\prod_{i=1}^{n-1}A_{a_{i}}\prod_{i=0}^{n-2}(1-\frac{1}{2^{b_{i}}})$
注意到仅关心于每一个$a_{i}$的数量,那么依次dp选择(要统计排列方案),并将其写成一个关于$\frac{1}{2^{x}}$的多项式,最终统计答案时$k$次项实际贡献即$\sum_{x\ge 0}(\frac{1}{2^{x}})^{k}=\frac{2^{k}}{2^{k}-1}$
dp状态为$o(n^{3})$(选到$i,$共选了$j$个$,k$次项系数),转移复杂度为$o(n)$(枚举$i$选几个),dp复杂度为$o(n^{4})$,对于所有$k$的总复杂度为$o(n^{5})$,可以通过
1 #include2 using namespace std; 3 #define N 50 4 #define mod 998244353 5 #define ll long long 6 int n,mi[N],inv_mi[N],fac[N],inv[N],A[N],a[N],g[N],f[N][N][N]; 7 int qpow(int n,int m){ 8 int s=n,ans=1; 9 while (m){ 10 if (m&1)ans=(ll)ans*s%mod; 11 s=(ll)s*s%mod,m>>=1; 12 } 13 return ans; 14 } 15 int calc(){ 16 int ans=0; 17 memset(f,0,sizeof(f)); 18 f[0][0][0]=1; 19 for(int i=0;i ){ 20 g[0]=1; 21 for(int j=1;j 1]*a[i]%mod; 22 for(int j=0;j ) 23 for(int k=0;j+k ) 24 for(int l=0;l<=n;l++){ 25 int s=(ll)f[i][j][l]*g[k]%mod*inv[k]%mod,s0=(ll)mi[i]*inv_mi[j+k]%mod; 26 if (i==n-1)f[i+1][j+k][l+1]=(f[i+1][j+k][l+1]+(ll)s*s0)%mod; 27 else{ 28 f[i+1][j+k][l+1]=(f[i+1][j+k][l+1]-(ll)s*s0%mod+mod)%mod; 29 f[i+1][j+k][l]=(f[i+1][j+k][l]+s)%mod; 30 } 31 } 32 } 33 for(int i=0;i<=n;i++)ans=(ans+(ll)f[n][n-1][i]*mi[i]%mod*qpow(mi[i]-1,mod-2))%mod; 34 ans=(ll)ans*fac[n-1]%mod*(mod+1>>1)%mod; 35 return ans; 36 } 37 int main(){ 38 mi[0]=inv_mi[0]=fac[0]=inv[0]=inv[1]=1; 39 for(int i=2;i mod; 40 for(int i=1;i ){ 41 mi[i]=(mi[i-1]<<1)%mod; 42 inv_mi[i]=(ll)(mod+1>>1)*inv_mi[i-1]%mod; 43 fac[i]=(ll)fac[i-1]*i%mod; 44 inv[i]=(ll)inv[i-1]*inv[i]%mod; 45 } 46 scanf("%d",&n); 47 int Inv=qpow(100,mod-2); 48 for(int i=0;i ){ 49 scanf("%d",&A[i]); 50 A[i]=(ll)A[i]*Inv%mod; 51 } 52 for(int i=0;i ){ 53 for(int j=0;j 1)%n]; 54 printf("%d ",calc()); 55 } 56 printf("\n"); 57 return 0; 58 }