Codeforces 891E - Lust(生成函数)
2024-10-16 22:44:24
NaCly_Fish:《简单》的生成函数题
然鹅我连第一步都没 observe 出来
首先注意到如果我们按题意模拟那肯定是不方便计算贡献的,因此考虑对题目的问法进行一些转化。《显然》,对于一种操作序列而言,其操作完之后答案的值,就是原来 \(a_i\) 的乘积减去操作后所有 \(a_i\) 的乘积,因为每次操作前后答案与所有 \(a_i\) 的乘积之和是个定值。因此问题可以转化为,求操作之后所有 \(a_i\) 的乘积的期望值。如果我们设 \(c_i\) 表示第 \(i\) 个数被操作的次数,那么操作之后 \(a_i\) 的乘积的期望值可以表示为
\[E(P)=\dfrac{1}{n^k}·\sum\limits_{\sum c_i=k}\dbinom{k}{c_1,c_2,\cdots,c_n}\prod\limits_{i=1}^n(a_i-c_i)
\]
\]
那么答案即为 \(\prod\limits_{i=1}^na_i-E(P)\)
考虑怎样求这个东西,注意到这里出现了 \(\sum c_i=k\),因此我们可以很自然地想到生成函数,又因为每次选择的位置是有顺序的,故此题涉及的是排列而不是组合问题,因此本题应采用 EGF,具体来说我们构造指数型生成函数 \(F_i(x)=\sum\limits_{v\ge 0}\dfrac{a_i-v}{v!}x^v\),那么重新审视一下上面的式子就可以得到
\[E(p)=\dfrac{k!}{n^k}[x^k]\prod\limits_{i=1}^nF_i(x)
\]
\]
直接把 \(F_i(x)\) 卷起来显然不合适,不过注意到这东西好像能跟 \(e^x\) 扯上关系,因此考虑化简:
\[\begin{aligned}
F_i(x)&=\sum\limits_{v\ge 0}\dfrac{a_i-v}{v!}x^v\\
&=\sum\limits_{v\ge 0}\dfrac{a_ix^v}{v!}-\sum\limits_{v\ge 1}\dfrac{x^v}{(v-1)!}\\
&=a_i\sum\limits_{v\ge 0}\dfrac{x^v}{v!}-x\sum\limits_{v\ge 0}\dfrac{x^v}{v!}\\
&=(a_i-x)e^x
\end{aligned}
\]
F_i(x)&=\sum\limits_{v\ge 0}\dfrac{a_i-v}{v!}x^v\\
&=\sum\limits_{v\ge 0}\dfrac{a_ix^v}{v!}-\sum\limits_{v\ge 1}\dfrac{x^v}{(v-1)!}\\
&=a_i\sum\limits_{v\ge 0}\dfrac{x^v}{v!}-x\sum\limits_{v\ge 0}\dfrac{x^v}{v!}\\
&=(a_i-x)e^x
\end{aligned}
\]
带回去
\[\dfrac{k!}{n^k}[x^k]e^{nx}\prod\limits_{i=1}^n(a_i-x)
\]
\]
考虑后面那个多项式
\[G(x)=\prod\limits_{i=1}^n(a_i-x)
\]
\]
我们考虑枚举其贡献给 \([x^k]\) 的系数,即
\[[x^k]e^xG(x)=\sum\limits_{i=0}^n[x^i]G(x)·[x^{k-i}]e^{nx}
\]
\]
即
\[[x^k]e^xG(x)=\sum\limits_{i=0}^n[x^i]G(x)·\dfrac{n^{k-i}}{(k-i)!}
\]
\]
带回去
\[\dfrac{k!}{n^k}\sum\limits_{i=0}^n[x^i]G(x)·\dfrac{n^{k-i}}{(k-i)!}
\]
\]
即
\[\sum\limits_{i=0}^n\dfrac{k!}{n^i(k-i)!}\sum\limits_{i=0}^n[x^i]G(x)
\]
\]
\(G(x)\) 的系数可以分治 NTT 做到 \(\mathcal O(n\log^2n)\),不过对于此题而言没有必要,\(n^2\) 递推即可。
const int MAXN=5000;
const int MOD=1e9+7;
int n,k,dp[MAXN+5];
int qpow(int x,int e){
int ret=1;
for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;
return ret;
}
int main(){
scanf("%d%d",&n,&k);dp[0]=1;
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
for(int j=i;~j;j--) dp[j]=(1ll*x*dp[j]-((!j)?0:dp[j-1])+MOD)%MOD;
} int ivn=qpow(n,MOD-2),res=dp[0];
for(int i=0,mul=1,pw=1;i<=n;i++){
res=(res-1ll*mul*dp[i]%MOD*pw%MOD+MOD)%MOD;
mul=1ll*mul*(k-i)%MOD;pw=1ll*pw*ivn%MOD;
}
printf("%d\n",res);
return 0;
}
最新文章
- RSA加密算法总结
- Regex
- 使用 xtrabackup 进行MySQL数据库物理备份
- localdomain的linux域
- chrome拓展开发实战
- POC - ASP.NET &; MYSQL部分
- Android Bitmap那些事之如何优化内存
- 关于通过adb启动Activity、activity、service以及发送broadcast的命令
- Tiny4412之C语言实现流水灯,Tiny4412裸机程序[3]
- android111 java中调用c代码
- cloudera安装hadoop集群和相关服务
- 安装 MYSQL exec: g++: not found 报错
- C#的数据类型总结(2):decimal ,double,float的区别
- Docker 网络管理及容器跨主机通信
- nginx——优化 Nginx 连接超时时间
- bzoj2830: [Shoi2012]随机树
- 了解一下,Java 虚拟机
- jxl 的详细用法说明
- Sql Server R8 密码问题及5102错误
- HDU 6006 状压dp