题目

给出一个数组A，经过一次处理，生成一个数组S，数组S中的每个值相当于数组A的累加，比如：A = {1 3 5 6} => S = {1 4 9 15}。如果对生成的数组S再进行一次累加操作，{1 4 9 15} => {1 5 14 29}，现在给出数组A，问进行K次操作后的结果。(输出结果 Mod 10^9 + 7)

分析

发现，每次处理相当于将A卷上一个I(∀ai=1)" role="presentation" style="position: relative;">I(∀ai=1)$I(\mathrm{\forall }{a}_i=1)$
于是机智的我在wiki又发现狄利克雷卷积满足交换律（我居然才知道）
于是快速幂咯，时间复杂度O(nlog2n)" role="presentation" style="position: relative;">O(nlog2n)$O(nlo{g}^{2}n)$，常数巨大，在51nod的老爷机上根本过不了。
然后就TLE得一塌糊涂。
于是找规律，发现ansk=∑i+j=kAiCj+n−1j" role="presentation" style="position: relative;">ansk=∑i+j=kAiCjj+n−1$an{s}_k=\sum _{i+j=k}{A}_i{C}_{j+n-1}^j$
然后NTT
但是，109+7" role="presentation" style="position: relative;">109+7${10}^9+7$并没有原根，所以祭出三模数NTT（如果有人想用高精度，我也没办法）。
因为(109+7)2∗n≈1023" role="presentation" style="position: relative;">(109+7)2∗n≈1023$({10}^9+7{)}^2\ast n\approx {10}^{23}$，所以找三个109" role="presentation" style="position: relative;">109${10}^9$左右的模数。
假设
ans≡a0(mod m0)" role="presentation">ans≡a0(mod m0)$$ans\equiv a_0(mod{m}_0)$$
ans≡a1(mod m1)" role="presentation">ans≡a1(mod m1)$$ans\equiv a_1(mod{m}_1)$$
ans≡a2(mod m2)" role="presentation">ans≡a2(mod m2)$$ans\equiv a_2(mod{m}_2)$$
因为m0m1m2" role="presentation" style="position: relative;">m0m1m2$m_0{m}_1{m}_2$会爆long long
所有，通过CRT（中国剩余定理）合并前两项，于是M=m0∗m1" role="presentation" style="position: relative;">M=m0∗m1$M=m_0\ast m_1$
ans≡A(mod M)" role="presentation">ans≡A(mod M)$$ans\equiv A(modM)$$
ans≡a2(mod m2)" role="presentation">ans≡a2(mod m2)$$ans\equiv a_2(mod{m}_2)$$
设ans=kM+A" role="presentation" style="position: relative;">ans=kM+A$ans=kM+A$
因为kM+A≡ans≡a2(mod m2)" role="presentation">kM+A≡ans≡a2(mod m2)$$kM+A\equiv ans\equiv a_2(mod{m}_2)$$
所以k≡(a2−A)M−1(mod m2)" role="presentation">k≡(a2−A)M−1(mod m2)$$k\equiv (a_2-A)M^{-1}(mod{m}_2)$$
那么根据上面的式子求出k，通过kM+A=ans" role="presentation" style="position: relative;">kM+A=ans$kM+A=ans$就可以求出ans了。 #include #include #include #include #include #include #include #include #include #include const int maxlongint=2147483647; const long long mo=1e9+7; const int N=200005; using namespace std; long long mod[3]={469762049,998244353,1004535809},M=mod[0]*mod[1],W[3][N]; long long f[3][N],g[3][N],v[3][N],v_[N],jc[3][N],ny[3][N],inv[N]; int n,m,fn; long long poww(long long x,long long y,int z) { long long s=1; x%=mod[z]; for(;y;x=x*x%mod[z],y>>=1) if(y&1) s=s*x%mod[z]; return s; } long long mul(long long x,long long y,long long mo) { long long s=0; x%=mo; for(;y;x=(x+x)%mo,y>>=1) if(y&1) s=(s+x)%mo; return s; } void NTT(long long *f,int type,int z) { for(int i=0,p=0;iif(ifor(int j=fn>>1;(p^=j)>=1); } for(int i=2;i<=fn;i<<=1) { int half=i>>1,pe=fn/i; for(int j=0;jlong long w=!type?W[z][j*pe]:W[z][fn-j*pe]; for(int k=j;klong long x=f[k],y=f[k+half]*w%mod[z]; f[k]=(x+y)%mod[z],f[k+half]=(x-y+mod[z])%mod[z]; } } } if(type) { long long ni=poww(fn,mod[z]-2,z); for(int i=0;imod[z]; } } long long CRT(long long a0,long long