CodeChefSeries Sum （伯努利数+生成函数+FFT）

Love The Way You Lie 2021-12-23 05:39 132阅读 0赞

## 题面 ##

[传送门][Link 1]

给定\\(a\_1,..,a\_n\\)，定义\\(f(x,k)=\\sum\_\{i=1\}^n(x+a\_i)^k,g(t,k)=\\sum\_\{x=0\}^tf(x,k)\\)，给定\\(T,K\\)，请你对\\(\\forall i\\in\[0,K\]\\)，求出\\(g(T,i)\\)，对\\(10^9+7\\)取模

## 前置芝士 ##

### 伯努利数 ###

什么？你不会伯努利数？那你先去看看[这篇文章][Link 2]

### \\(MTT\\) ###

什么？看到这模数你说你不会\\(MTT\\)？出门左转洛谷模板区啥都有

## 题解 ##

cjj拿着这题来问咱，咱发现自己跟个白痴一样啥也不会……

好毒瘤啊……虽然过了样例之后就\\(1A\\)了比较爽……但这还是多项式啊……

首先，对\\(f(x,k)\\)，有

\\\[ \\begin\{aligned\} f(x,k) &=\\sum\_\{i=1\}^n(x+a\_i)^k\\\\ &=\\sum\_\{i=1\}^n\\sum\_\{j=0\}^k\{k\\choose j\}x^j\{a\_i\}^\{k-j\}\\\\ &=\\sum\_\{j=0\}^k\{k\\choose j\}x^j\\sum\_\{i=1\}^n\{a\_i\}^\{k-j\}\\\\ \\end\{aligned\} \\\]

然后对\\(g(t,k)\\)，有

\\\[ g(t,k)=\\sum\_\{x=0\}^t\\sum\_\{j=0\}^k\{k\\choose j\}x^j\\sum\_\{i=1\}^n\{a\_i\}^\{k-j\} \\\]

写成卷积形式

\\\[ \{g(t,k)\\over k!\}=\\sum\_\{j=0\}^k\{\\sum\_\{x=0\}^tx^j\\over j!\}\{\\sum\_\{i=1\}^n\{a\_i\}^\{k-j\}\\over (k-j)!\} \\\]

我们需要求出\\(G(x)\\)的第\\(k\\)项的系数乘上\\(k!\\)就是题目中所说的\\(g(T,k)\\)的答案

所以我们现在需要快速求出后面两个多项式的系数

## 左边 ##

令左边的多项式为\\(F(x)\\)，这是一个关于自然数幂和的东西，那么就得上伯努利数了

不过注意正常的伯努利数求自然数幂和是\\(\\sum\_\{i=0\}^\{n-1\}i^k\\)而这里是\\(\\sum\_\{i=0\}^\{n\}i^k\\)，不要忘了加上\\(n^k\\)

然后接下来就是推倒的时间

\\\[ \\begin\{aligned\} \\left\[x^k\\right\]F &=\\sum\_\{i=0\}^ti^k\\\\ &=t^k+\{1\\over k+1\}\\sum\_\{i=0\}^k\{k+1\\choose i\}B\_it^\{k+1-i\}\\\\ &=t^k+k!\\sum\_\{i=0\}^k\{B\_i\\over i!\}\{t^\{k+1-i\}\\over (k+1-i)!\} \\end\{aligned\} \\\]

已经可以写成卷积的形式了，卷积出来的柿子的第\\(k+1\\)项乘上\\(k!\\)加上\\(t^k\\)就是\\(\[x^k\]F\\)了

不过注意卷积的柿子中并没有\\(\{B\_\{k+1\}\\over \{(k+1)!\}\}\\times \{t^0\\over 0!\}\\)这一项，所以要把\\(\{t^0\\over 0!\}\\)设为\\(0\\)才行

顺便注意\\(\[x^0\]F\\)应该是\\(t+1\\)

## 右边 ##

令第二个多项式为\\(A(z)\\)，有

\\\[ \\begin\{aligned\} A(x)=\\sum\_\{i=0\}^\\infty x^i\{\\sum\_\{k=1\}^n\{a\_k\}^i\\over i!\} \\end\{aligned\} \\\]

然后继续推倒

\\\[ \\begin\{aligned\} A(x) &=\\sum\_\{i=0\}^\\infty x^i\\sum\_\{j=1\}^n\{a\_j\}^i\\\\ &=\\sum\_\{j=1\}^n\\sum\_\{i=0\}^\\infty \{a\_j\}^ix^i\\\\ &=\\sum\_\{i=1\}^n\{1\\over 1-a\_ix\}\\\\ &=\\sum\_\{i=1\}^n \{a\_i\}^0+\{a\_i\}^1x^1+\{a\_i\}^2x^2+... \\end\{aligned\} \\\]

所以……这玩意儿该咋算啊……

我们设

\\\[ \\begin\{aligned\} G(x) &=\\sum\_\{i=1\}^n\{-a\_i\\over 1-a\_ix\}\\\\ &=\\sum\_\{i=1\}^n-\{a\_i\}^1-\{a\_i\}^2x-\{a\_i\}^3x^2-...\\\\ \\end\{aligned\} \\\]

那么就有\\(A(x)=-xG(x)+n\\)

然而我还是不会算\\(G\\)啊……

那就继续推倒

\\\[ \\begin\{aligned\} G(x) &=\\sum\_\{i=1\}^n\{-a\_i\\over 1-a\_ix\}\\\\ &=\\sum\_\{i=1\}^n\\ln'\\left(1-a\_ix\\right)\\\\ &=\\ln'\\left(\\prod\_\{i=1\}^n (1-a\_ix)\\right) \\end\{aligned\} \\\]

分治\\(NTT\\)就行啦

然后没有然后了

记得思路清晰一点

//minamoto #include<bits/stdc++.h> #define R register #define ll long long #define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i) #define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i) #define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v) using namespace std; char buf[1<<21],*p1=buf,*p2=buf; inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;} int read(){ R int res,f=1;R char ch; while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1); for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); return res*f; } ll readll(){ R ll res,f=1;R char ch; while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1); for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0'); return res*f; } char sr[1<<21],z[20];int C=-1,Z=0; inline void Ot(){fwrite(sr,1,C+1,stdout),C=-1;} void print(R int x){ if(C>1<<20)Ot();if(x<0)sr[++C]='-',x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++C]=z[Z],--Z);sr[++C]=' '; } const int N=(1<<18)+5,P=1e9+7;const double Pi=acos(-1.0); inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;} inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;} inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;} int ksm(R int x,R int y){ R int res=1; for(;y;y>>=1,x=mul(x,x))if(y&1)res=mul(res,x); return res; } struct cp{ double x,y; cp(R double xx=0,R double yy=0){x=xx,y=yy;} inline cp operator +(const cp &b)const{return cp(x+b.x,y+b.y);} inline cp operator -(const cp &b)const{return cp(x-b.x,y-b.y);} inline cp operator *(const cp &b)const{return cp(x*b.x-y*b.y,x*b.y+y*b.x);} }rt[2][N<<1]; int r[21][N],inv[N],fac[N],ifac[N],B[N],A[N],d,lim; inline void init(R int len){lim=1,d=0;while(lim<len)lim<<=1,++d;} void FFT(cp *A,int ty){ fp(i,0,lim-1)if(i<r[d][i])swap(A[i],A[r[d][i]]); cp t; for(R int mid=1;mid<lim;mid<<=1) for(R int j=0;j<lim;j+=(mid<<1)) fp(k,0,mid-1) A[j+k+mid]=A[j+k]-(t=A[j+k+mid]*rt[ty][mid+k]), A[j+k]=A[j+k]+t; if(!ty){ double k=1.0/lim; fp(i,0,lim-1)A[i].x*=k; } } void MTT(int *a,int *b,int len,int *c){ init(len<<1); static cp A[N],B[N],C[N],D[N],F[N],G[N],H[N]; fp(i,0,len-1){ A[i].x=a[i]>>15,B[i].x=a[i]&32767, C[i].x=b[i]>>15,D[i].x=b[i]&32767, A[i].y=B[i].y=C[i].y=D[i].y=0; }fp(i,len,lim-1)A[i]=B[i]=C[i]=D[i]=0; FFT(A,1),FFT(B,1),FFT(C,1),FFT(D,1); fp(i,0,lim-1)F[i]=A[i]*C[i],G[i]=A[i]*D[i]+B[i]*C[i],H[i]=B[i]*D[i]; FFT(F,0),FFT(G,0),FFT(H,0); fp(i,0,lim-1)c[i]=(((ll)(F[i].x+0.5)%P<<30)+((ll)(G[i].x+0.5)<<15)+((ll)(H[i].x+0.5)))%P; } void Inv(int *a,int *b,int len){ if(len==1)return b[0]=ksm(a[0],P-2),void(); Inv(a,b,len>>1); static int c[N],d[N]; MTT(a,b,len,c),MTT(b,c,len,d); fp(i,0,len-1)b[i]=dec(add(b[i],b[i]),d[i]); } void Ln(int *a,int *b,int len){ static int A[N],B[N]; fp(i,1,len-1)A[i-1]=mul(a[i],i);A[len-1]=0; Inv(a,B,len),MTT(A,B,len,A); fp(i,1,len-1)b[i]=mul(A[i-1],inv[i]);b[0]=0; } void Pre(){ fp(d,1,18)fp(i,1,(1<<d)-1)r[d][i]=(r[d][i>>1]>>1)|((i&1)<<(d-1)); inv[0]=fac[0]=ifac[0]=inv[1]=fac[1]=ifac[1]=1; fp(i,2,262144){ fac[i]=mul(fac[i-1],i), inv[i]=mul(P-P/i,inv[P%i]), ifac[i]=mul(ifac[i-1],inv[i]); } for(R int i=1;i<=262144;i<<=1)fp(k,0,i-1) rt[1][i+k]=cp(cos(Pi*k/i),sin(Pi*k/i)),rt[0][i+k]=cp(cos(Pi*k/i),-sin(Pi*k/i)); fp(i,0,65535)A[i]=ifac[i+1]; Inv(A,B,1<<16); fp(i,0,65535)B[i]=mul(B[i],fac[i]); } int D[21][N],a[N]; void solve(int d,int l,int r){ if(l==r)return D[d][0]=1,D[d][1]=P-a[l],void(); int mid=(l+r)>>1; solve(d,l,mid),solve(d+1,mid+1,r); init(max(mid-l+1,r-mid)+1); int len=lim; fp(i,mid-l+2,len-1)D[d][i]=0; fp(i,r-mid+1,len-1)D[d+1][i]=0; MTT(D[d],D[d+1],len,D[d]); fp(i,r-l+2,(len<<1)-1)D[d][i]=0; } void calc(int *a,int *b,int n,int t){ static int A[N],B[N]; solve(1,1,n); init(t+1);int len=lim; fp(i,0,n)A[i]=D[1][i]; fp(i,n+1,len-1)A[i]=0; Ln(A,B,len); fp(i,1,len-1)B[i-1]=mul(B[i],i);B[len-1]=0; b[0]=n; fp(i,1,t)b[i]=mul(P-B[i-1],ifac[i]); } int ak[N],bk[N],bin[N],F[N],G[N],n,k,t; void MAIN(){ bin[0]=1;fp(i,1,k+k)bin[i]=mul(bin[i-1],t); int len=1;while(len<k+2)len<<=1; fp(i,0,len-1)F[i]=mul(B[i],ifac[i]),G[i]=mul(bin[i],ifac[i]); G[0]=0; MTT(F,G,len,F); ak[0]=t+1; fp(i,1,k)ak[i]=add(bin[i],mul(fac[i],F[i+1])),ak[i]=mul(ak[i],ifac[i]); calc(a,bk,n,k); len=1;while(len<k)len<<=1; fp(i,k+1,len-1)ak[i]=bk[i]=0; MTT(ak,bk,len,ak); fp(i,0,k)print(mul(ak[i],fac[i])); } int main(){ // freopen("testdata.in","r",stdin); Pre(); n=read(),k=read(),t=readll()%P; fp(i,1,n)a[i]=read(); MAIN(); return Ot(),0; }

转载于:https://www.cnblogs.com/bztMinamoto/p/10539897.html

[Link 1]: https://www.codechef.com/problems/SERSUM
[Link 2]: https://www.cnblogs.com/bztMinamoto/p/10534777.html