卡精度的任意模数fft模板题……
这道题随便写个表就能看出规律来(或者说考虑一下实际意义),反正拿到这题之后,很快就会发现他是任意模数fft模板题.
然后我就去网上抄了一下板子……
我打的是最土的任意模数fft,就是fft7次的那种……(好像有很多方法的样子……)
这种任意模数fft方法见http://blog.csdn.net/l_0_forever_lf/article/details/52886397
这道题的具体做法见http://blog.csdn.net/qq_33229466/article/details/78837522
这种方法的思想就是:
I.既然出题人给出了任意模数的多项式乘法,那么常规ntt肯定是不行
II.既然他取模,那数会很大,会炸精,常规的fft也不行
III.既然直接乘会炸精,那我们就把数变小,多跑几次也没关系
(IV.感觉加了一维卷积,有种这种方法很妙,可以继续扩展的感觉,但是很模糊,也说不具体)
本着这种思路,我们逆变换的时候,不能在点值表达式直接操作,最后一遍回去,因为这样效果和没有在一开始把数缩小一样,会炸精.
最后说一下这道题的坑点:如果你不预处理复数,你会炸精.
好像有的人没有预处理,但是用了long double,就没有被卡……
似乎cmath库里有标准库也有类库,而且有的函数两者并不都具有,但是最坑爹的一点是对于sin,cos等函数,cmath标准库的精度大于cmath类库……(这只是我经过亲身试验做出的推测)
反正预处理就没有这些破事……
#include <cmath>
#include <cstdio>
#include <cstring>
#include <complex>
#include <algorithm>
typedef long long LL;
typedef double db;
typedef std::complex<db> cd;
const int N=;
const db Pai=acos((db)-);
const int P=;
cd a1[N],b1[N],a2[N],b2[N],c1[N],c2[N],c3[N],w1[N],w2[N];
int rev[N],len;
int ai[N],bi[N],ans[N],ni[N];
inline void fft(cd *C,int opt,cd *wn){
register int i,j,k;cd temp;
for(i=;i<len;++i)if(rev[i]>i)std::swap(C[i],C[rev[i]]);
for(k=;k<=len;k<<=){
for(i=;i<len;i+=k){
for(j=;j<(k>>);++j){
temp=C[i+j+(k>>)]*wn[len/k*j];
C[i+j+(k>>)]=C[i+j]-temp;
C[i+j]+=temp;
}
}
}
if(opt==-){
db inv=./len;
for(i=;i<len;++i)C[i]*=inv;
}
}
inline void Mul(int *a,int *b,int *c,int n){
len=;
while(len<n)len<<=;
int i,sqr=sqrt(P);
cd temp;
for(i=;i<len;++i)rev[i]=(rev[i>>]>>)|((i&)?(len>>):);
for(i=;i<len;++i){
w1[i]=cd(std::cos(.*Pai/len*i),std::sin(.*Pai/len*i));
w2[i]=cd(std::cos(-.*Pai/len*i),std::sin(-.*Pai/len*i));
}
for(i=;i<len;++i){
a1[i]=ai[i]/sqr,b1[i]=ai[i]%sqr;
a2[i]=bi[i]/sqr,b2[i]=bi[i]%sqr;
}
fft(a1,,w1),fft(b1,,w1),fft(a2,,w1),fft(b2,,w1);
for(i=;i<len;++i){
c1[i]=a1[i]*a2[i];
c2[i]=a1[i]*b2[i]+a2[i]*b1[i];
c3[i]=b1[i]*b2[i];
}
fft(c1,-,w2),fft(c2,-,w2),fft(c3,-,w2);
for(i=;i<len;++i)
c[i]=((LL)(round(c1[i].real()))%P*sqr%P*sqr%P+(LL)(round(c2[i].real()))%P*sqr%P+(LL)(round(c3[i].real()))%P)%P;
}
int main(){
int n,k,i;
scanf("%d%d",&n,&k);
for(i=;i<n;++i)scanf("%d",&ai[i]);
bi[]=;
for(i=;i<n;++i)
bi[i]=(LL)bi[i-]*(k+i-)%P*(i==?ni[i]=:ni[i]=(-(LL)(P/i)*ni[P%i]%P+P)%P)%P;
Mul(ai,bi,ans,n<<);
for(i=;i<n;++i)printf("%d\n",ans[i]);
return ;
}