相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3992
Latex题面:http://paste.ubuntu.com/23997878/
数据生成器:http://paste.ubuntu.com/24006205/
神犇题解:http://www.cnblogs.com/gromah/p/4431016.html
NTT相关:http://blog.miskcoo.com/2015/04/polynomial-multiplication-and-fast-fourier-transform#i-13
解题报告
这题$O(m^3logn)$的基于矩阵快速幂的算法大家都会吧?
然而只能通过 $60\% $ 的数据 QwQ
然后就需要一点黑科技了
考虑模数这么奇怪,于是可能是用元根来搞一搞
然后我们发现,我们可以用元根的幂次来表示 $0 \sim m – 1$ 的每一个数
于是我们就可以把乘法换成幂次的加法,于是就可以搞NTT了!
于是用NTT来搞生成函数,复杂度:$O(nmlogm)$
然后再套上一开始讲的快速幂,那么就是$O(mlogmlogn)$的复杂度啦!
Code
话说这似乎是第一次撸$NTT$呢!
还有一点小激动啊!
不过这一份代码封装太多了,好慢啊 QwQ
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 9000; const int M = N << 2; const int MOD = 1004535809; int l,n,m,x,pos[N]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline int Pow(int w, int t, int mod) { int ret = 1; for (;t;t>>=1,w=(LL)w*w%mod) if (t & 1) ret = (LL)ret * w % mod; return ret; } inline int Get_Primitive_Root(int w) { vector<int> pri; int cur = w - 1; for (int i=2,lim=ceil(sqrt(w));i<=cur&&i<=lim;i++) { if (cur % i == 0) { pri.push_back(i); while (cur % i == 0) cur /= i; } } if (cur > 1) pri.push_back(cur); if (pri.empty()) return 2; for (int i=2;;i++) { for (int j=pri.size()-1;j>=0;j--) { if (Pow(i, w/pri[j], w) == 1) break; if (!j) return i; } } } struct Sequence{ int a[M],POS[M],len; inline Sequence() {} inline Sequence(int l) { memset(a,0,sizeof(a)); len = l; a[0] = 1; } inline Sequence(Sequence &B) { memcpy(this, &B, sizeof(B)); len=B.len; } inline void NTT(int f) { static const int G = Get_Primitive_Root(MOD); int l = -1; for (int i=len;i;i>>=1) l++; if (!POS[1]) { for (int i=1;i<len;i++) { POS[i] = POS[i>>1]>>1; if (i & 1) POS[i] |= 1 << l-1; } } for (int i=0;i<len;i++) if (POS[i] > i) swap(a[i], a[POS[i]]); for (int seg=2;seg<=len;seg<<=1) { int wn = Pow(G, MOD/seg, MOD); if (f == -1) wn = Pow(wn, MOD-2, MOD); for (int i=0;i<len;i+=seg) { for (int k=i,w=1;k<i+seg/2;k++,w=(LL)w*wn%MOD) { int tmp = (LL)w * a[k+seg/2] % MOD; a[k+seg/2] = ((a[k] - tmp) % MOD + MOD) % MOD; a[k] = (a[k] + tmp) % MOD; } } } if (f == -1) { for (int i=0,rev=Pow(len,MOD-2,MOD);i<len;i++) a[i] = (LL)a[i] * rev % MOD; } } inline void Multiply(Sequence B) { NTT(1); B.NTT(1); for (int i=0;i<len;i++) a[i] = (LL)a[i] * B.a[i] % MOD; NTT(-1); for (int i=m-1;i<len;i++) (a[i-m+1] += a[i]) %= MOD, a[i] = 0; } inline void pow(int t) { Sequence ret(len),w(*this); for (;t;t>>=1,w.Multiply(w)) if (t & 1) ret.Multiply(w); memcpy(this, &ret, sizeof(ret)); } }arr; int main() { l = read(); m = read(); x = read() % m; n = read(); int PRT = Get_Primitive_Root(m); for (int cur=1,i=0;i<m-1;i++,cur=cur*PRT%m) pos[cur] = i; for (int i=0,t;i<n;i++) t=read(), t?arr.a[pos[t%m]]++:0; int len = 1; while (len < m) len <<= 1; arr.len = len << 1; arr.pow(l); printf("%d\n",(arr.a[pos[x]]+MOD)%MOD); return 0; }