YbtOJ 976「母函数」随机减法
题目链接：YbtOJ #976
小 A 有一个长度为 n 的序列 a 和一个初始值为 0 的计数器 cnt，他想要对其进行 k 次操作。
每次操作，他会等概率随机选中一个 i，将 a_i 减 1，并将 cnt 加上 此时 除 a_i 以外所有数的乘积，即 prod_{jnot=i}a_j。
现在，他希望知道 cnt 在模 10^9 7 意义下的期望值。
1le nle5times10^3，1le kle10^9，0le a_i < 10^9 7
Solution
容易发现将 a_i 减 1 后，除它以外所有数的乘积恰好是 prod_{i=1}^na_i 的变化量。
所以说，答案实际上就是原本的 prod_{i=1}^na_i 减去修改后 prod_{i=1}^na_i’ 的期望值。
设 f_{i,j} 表示前 i 个数一共修改了 j 次的所有方案下乘积之和，则：
于是：
设 F_i(x)=sum_{p=0}^{ infty}f_{i,p}frac{x^p}{p!},G_i(x)=sum_{p=0}^{ infty}(a_i-p)frac{x^p}{p!}，得到：
因此只要把 G_{1sim n}(x) 这 n 个生成函数卷起来就能得到 F_n(x)，而它的 k 次项系数就是 frac{f_{n,k}}{k!} 了。
对于 G_i(x)，我们把 a_i-p 分开来：
设 A_i(x)=a_i-x，发现 F_n(x) 就是 A_{1sim n}(x) 这 n 个生成函数卷起来之后再卷上 e^{nx}。
很容易 O(n^2) 暴力求出 A_{1sim n}(x) 卷起来后每一项的系数 f_i，于是：
乘上一个 k! 得到了总和 f_{n,k}，再除以总方案数 n^k 得到期望：
最终答案就是prod_{i=1}^na_i-E。
注意一开始卷积直接暴力卷即可。
Code
代码语言：javascript复制#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI) fread(FI,1,FS,stdin),FA==FB)?EOF:*FA )
#define pc(c) (FC==FE&&(clear(),0),*FC =c)
int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO FS;
I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
Tp I void read(Ty& x) {x=0;RI f=1;W(!isdigit(oc=tc())) f=oc^'-'?1:-1;W(x=(x<<3) (x<<1) (oc&15),isdigit(oc=tc()));x*=f;}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(OS[ OT]=x 48,x/=10);W(OT) pc(OS[OT--]);}
Tp I void writeln(Ty x) {x<0&&(pc('-'),x=-x);W(OS[ OT]=x 48,x/=10);W(OT) pc(OS[OT--]);pc('n');}
}using namespace FastIO;
Cn int N=5e3 10,XX=1e9 7;
int n,k,a[N],sa[N],sb[N],ic[N],Ans;
I int QP(RI a,RI b,CI p=XX){RI s=1;W(b) b&1&&(s=1LL*s*a%p),a=1LL*a*a%p,b>>=1;return s;}
// class Poly{
// private:
// int P,L,R[N<<2],B[N<<2];
// I void NTT(int *s,CI op){
// RI i,j,k,x,y,U,S;for(i=0;i<P;i ) i<R[i]&&(swap(s[i],s[R[i]]),0);
// for(i=1;i<P;i<<=1) for(U=QP(QP(3,op,X),(X-1)/(i<<1),X),j=0;j<P;j =i<<1)
// for(S=1,k=0;k<i;k ,S=1LL*S*U%X) s[j k]=((x=s[j k]) (y=1LL*S*s[i j k]%X))%X,s[i j k]=(x-y X)%X;
// }
// public:
// int X,A[N<<2];
// I void Mul(CI n,int *a,CI m,int *b){
// RI i,t;P=1,L=0;W(P<=n m) P<<=1, L;for(i=0;i<P;i ) R[i]=(R[i>>1]>>1)((i&1)<<L-1);
// for(i=0;i<P;i ) A[i]=B[i]=0;for(i=0;i<=n;i ) A[i]=a[i];for(i=0;i<=m;i ) B[i]=b[i];
// for(NTT(A,1),NTT(B,1),i=0;i<P;i ) A[i]=1LL*A[i]*B[i]%X;
// for(t=QP(P,X-2,X),NTT(A,X-2),i=0;i<=n m;i ) A[i]=1LL*A[i]*t%X;
// }
// }T[3];
// I LL CRT(LL r1,LL p1,LL r2,LL p2,CI fg){
// LL k=1LL*((r2-r1)%p2 p2)*QP(p1%p2,p2-2,p2)%p2;
// return fg?((p1%XX)*k r1)%XX:(p1*k r1)%(p1*p2);
// }
// I void Mul(CI n,int *a,CI m,int *b){
// RI i;for(i=0;i<3;i ) T[i].Mul(n,a,m,b);
// for(i=0;i<=n m;i ) a[i]=CRT(CRT(T[0].A[i],T[0].X,T[1].A[i],T[1].X,0),1LL*T[0].X*T[1].X,T[2].A[i],T[2].X,1);
// }
int T[N];
I void Mul(CI n,int *a,CI m,int *b){
RI i,j;for(i=0;i<=n m;i ) T[i]=0;
for(i=0;i<=n;i ) for(j=0;j<=m;j ) T[i j]=(1LL*a[i]*b[j]%XX T[i j])%XX;
for(i=0;i<=n m;i ) a[i]=T[i];
}
int main(){
freopen("calculate.in","r",stdin),freopen("calculate.out","w",stdout);
RI i,t;for(read(n,k),Ans=i=1;i<=n;i ) read(a[i]),Ans=1LL*Ans*a[i]%XX;//T[0].X=998244353,T[1].X=469762049,T[2].X=1004535809;
for(sa[0]=a[1],sa[1]=XX-1,i=2;i<=n;i ) sb[0]=a[i],sb[1]=XX-1,Mul(i-1,sa,1,sb);
for(ic[n]=QP(QP(n,n),XX-2),i=n-1;~i;i--) ic[i]=1LL*ic[i 1]*n%XX;
for(t=1,i=0;i<=n;i ) Ans=(XX-1LL*sa[i]*t%XX*ic[i]%XX Ans)%XX,t=1LL*t*(k-i)%XX;
return writeln(Ans),cerr<<clock()<<'n',clear(),0;
}
