2018秦皇岛ccpc

秦皇岛ccpc"/>

2018秦皇岛ccpc

因为给定的模数P保证是素数,所以P一定有原根.
根据原根的性质,若\(g\)是\(P\)的原根,则\(g^k\)能够生成\([1,P-1]\)中所有的数,这样的k一共有P-2个.
则\(a_i*a_j(mod\ P)=a_k\) 就可以转化为\(g^i*g^j(mod\ P) = g^{i+j}(mod\ P)=g^k\).
问题转化为了求有多少对有序的<i,j>满足 \((i+j)(mod\ (P-1)) = k\).
求出原根后,对\([1,P-1]\)中的每个数编号, 统计每个编号出现的次数,然后FFT求卷积
要特判0,因为原根不会生成0.所以用总的有序对数-其他不含0的有序对数得到含0的有序对,这是0的答案;超过P-1的数肯定没有符合的有序对.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 2e5+5;
bool notpri[maxn];
int pri[maxn],zyz[maxn];
typedef long long LL;void pre(int N){notpri[1]=1;for(int i=2;i<N;++i){if(!notpri[i]){pri[++pri[0]]=i;}for(int j=1;j<=pri[0] && (LL)i*(LL)pri[j]<N;++j){notpri[i*pri[j]]=1;if(i%pri[j]==0){break;}}}
}
LL Quick_Pow(LL x,LL p,LL mod){if(!p){return 1ll;}LL res=Quick_Pow(x,p>>1,mod);res=res*res%mod;if((p&1ll)==1ll){res=(x%mod*res)%mod;}return res;
}
int FindRoot(int x){/*求素奇数的最小原根，倘若x不是奇数，但是也有原根的话，将质
因子分解改成对phi(x)即可。倘若要求多个原根，直接接着暴力验证即可*/int tmp=x-1;for(int i=1;tmp && i<=pri[0];++i){if(tmp%pri[i]==0){zyz[++zyz[0]]=pri[i];while(tmp%pri[i]==0){tmp/=pri[i];}}}for(int g=2;g<=x-1;++g){bool flag=1;for(int i=1;i<=zyz[0];++i){if(Quick_Pow((LL)g,(LL)((x-1)/zyz[i]),(LL)x)==1){flag=0;break;}}if(flag){return g;}}return 0;
}const int MAXN = 4e5 + 10;
const double PI = acos(-1.0);
struct Complex{double x, y;inline Complex operator+(const Complex b) const {return (Complex){x +b.x,y + b.y};}inline Complex operator-(const Complex b) const {return (Complex){x -b.x,y - b.y};}inline Complex operator*(const Complex b) const {return (Complex){x *b.x -y * b.y,x * b.y + y * b.x};}
} va[MAXN * 2 + MAXN / 2], vb[MAXN * 2 + MAXN / 2];
int lenth = 1, rev[MAXN * 2 + MAXN / 2];
int N, M;   // f 和 g 的数量//f g和 的系数// 卷积结果// 大数乘积
int f[MAXN],g[MAXN];
vector<LL> conv;
vector<LL> multi;
//f g
void init()
{int tim = 0;lenth = 1;conv.clear(), multi.clear();memset(va, 0, sizeof va);memset(vb, 0, sizeof vb);while (lenth <= N + M - 2)lenth <<= 1, tim++;for (int i = 0; i < lenth; i++)rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (tim - 1));
}
void FFT(Complex *A, const int fla)
{for (int i = 0; i < lenth; i++){if (i < rev[i]){swap(A[i], A[rev[i]]);}}for (int i = 1; i < lenth; i <<= 1){const Complex w = (Complex){cos(PI / i), fla * sin(PI / i)};for (int j = 0; j < lenth; j += (i << 1)){Complex K = (Complex){1, 0};for (int k = 0; k < i; k++, K = K * w){const Complex x = A[j + k], y = K * A[j + k + i];A[j + k] = x + y;A[j + k + i] = x - y;}}}
}
void getConv(){             //求多项式init();for (int i = 0; i < N; i++)va[i].x = f[i];for (int i = 0; i < M; i++)vb[i].x = g[i];FFT(va, 1), FFT(vb, 1);for (int i = 0; i < lenth; i++)va[i] = va[i] * vb[i];FFT(va, -1);for (int i = 0; i <= N + M - 2; i++)conv.push_back((LL)(va[i].x / lenth + 0.5));
}LL vz[MAXN];
int id[MAXN];
int cnt[MAXN];
int rnk[MAXN];
LL ans[MAXN];int main()
{#ifndef ONLINE_JUDGEfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifpre(maxn-1);int n,P ;scanf("%d %d",&n, &P);int rt = FindRoot(P);memset(id,0,sizeof(id));LL idx = 1;for(int i=0;i<P-1;++i){         //一共只有[0,P-2],P-1个idid[idx] = i;rnk[i]= idx;idx = idx*rt%P;}for(int i=1;i<=n;++i){LL tmp;scanf("%lld",&tmp);vz[i] = tmp;tmp%=P;if(tmp==0) continue;        //卷积中不考虑0的贡献cnt[id[tmp]]++;}N = M = P;for(int i=0;i<P-1;++i){f[i] = g[i] = cnt[i];}getConv();int sz = conv.size();for(int i=0;i<sz;++i){LL tmp = conv[i];ans[rnk[i%(P-1)]] += tmp;}LL tot = (LL)n*n;           //全部的枚举可能-不选0之外的组合 = 包含0的组合for(int i=1;i<P;++i){tot -= ans[i];}ans[0] = tot;for(int i=1;i<=n;++i){if(vz[i]>=P) printf("0\n");else{printf("%lld\n",ans[vz[i]]);}}return 0;
}

转载于:.html