【wanaflyCamp】Steins;Gate(原根+FFT)

Steins;Gate(原根+FFT)"/>

【wanaflyCamp】Steins;Gate(原根+FFT)

思路：利用原根吧乘运算变成加运算，然后fft，但是不知道为什么就是过不去啊。。。
先把有问题的代码先贴一下，过会在调试一下：
代码已更新：终于通过拉，开熏！！！
代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#define maxx 200005
#define maxn 505
#define ll long long
using namespace std;
bool isP[maxn];
int prime[maxn];
int cnt=0;
void init()
{for(int i=2;i<maxn;i++){if(!isP[i])prime[cnt++]=i;for(int j=0;j<cnt&&i*prime[j]<maxn;j++){isP[i*prime[j]]=true;if(i%prime[j]==0)break;}}
}
int fac[20];
int k;
void getFac(int num)
{k=0;for(int i=0;prime[i]*prime[i]<=num;i++){if(num%prime[i]==0){fac[k++]=prime[i];while(num%prime[i])num/=prime[i];}}if(num>1)fac[k++]=num;
}
ll P(ll a,ll b,ll mod)
{ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod;b>>=1;}return ans;
}
bool check(int num,int p)
{getFac(p-1);for(int i=0;i<k;i++)if(P(num,(p-1)/fac[i],p)==1)return false;return true;    
}
int getRoot(int p)
{for(int i=2;;i++)if(check(i,p)) return i; 
}
const double pi=acos(-1.0);
struct Complex
{double x,y;Complex(double _x=0,double _y=0){x=_x;y=_y;}Complex operator-(const Complex &b)const{return Complex(x-b.x,y-b.y);}Complex operator +(const Complex &b)const{return Complex(x+b.x,y+b.y);}Complex operator*(const Complex &b)const{return Complex(x*b.x-y*b.y,x*b.y+y*b.x);}
};
void change(Complex y[],int len)
{for(int i=1,j=len>>1;i<len-1;i++){if(i<j)swap(y[i],y[j]);int k=len>>1;while(j>=k){j-=k;k/=2;}if(j<k)j+=k;}
}
void fft(Complex y[],int len,int on)
{change(y,len);for(int h=2;h<=len;h<<=1){Complex wn(cos(-on*2*pi/h),sin(-on*2*pi/h));for(int j=0;j<len;j+=h){Complex w(1,0);for(int k=j;k<j+h/2;k++){Complex u=y[k];Complex t=w*y[k+h/2];y[k]=u+t;y[k+h/2]=u-t;w=w*wn;}}}if(on==-1)for(int i=0;i<len;i++)y[i].x/=len; 
}
int a[maxx], _a[maxx];
int I[maxx];
int num[maxx];
ll zero=0;
Complex _x[maxx<<2];
ll c[maxx<<2];
int main()
{init();int n,p;cin>>n>>p;int root=getRoot(p);ll now=1;for(int i=1;i<p;i++){now=now*root%p;I[now]=i;}I[1]=0;//for(int i=1;i<p;i++) cout<<I[i]<<" ";for(int i=1;i<=n;i++){scanf("%d",a+i);_a[i]=a[i]%p;if(_a[i])num[I[_a[i]]]++;else zero++;}//for(int i=0;i<p-1;i++)cout<<num[i]<<" ";int _len=p-1;int len=1;while(len<2*_len)len<<=1;for(int i=0;i<_len;i++)_x[i]=Complex(num[i],0);for(int i=_len;i<len;i++)_x[i]=Complex(0,0);fft(_x,len,1);for(int i=0;i<len;i++)_x[i]=_x[i]*_x[i];fft(_x,len,-1);for(int i=0;i<len;i++)c[i]=(ll)(_x[i].x+0.5);len= p-1+p-2;//for(int i=0;i<len;i++)cout<<c[i]<<" ";//cout<<endl;for(int i=p-1;i<len;i++)c[i%(p-1)]+=c[i];ll ansZ=zero*(n-zero)*2+zero+zero*(zero-1);for(int i=1;i<=n;i++){if(a[i]>=p)printf("0\n");else{if(_a[i])printf("%lld\n",c[I[_a[i]]]);else printf("%lld\n",ansZ);}}return 0;
}/**************************************************************Problem: 1053User: coldfreshLanguage: C++Result: 正确Time:756 msMemory:23456 kb
****************************************************************/