题解
这个乘积比较麻烦, 转换成原根的指数乘法就相当于指数加和了, 可以 NTT 优化
注意判掉 0
代码
- #include <bits/stdc++.h>
- #define fi first
- #define se second
- #define pii pair<int,int>
- #define pdi pair<db,int>
- #define mp make_pair
- #define pb push_back
- #define enter putchar('\n')
- #define space putchar(' ')
- #define eps 1e-8
- #define mo 974711
- #define MAXN 1000005
- //#define ivorysi
- using namespace std;
- typedef long long int64;
- typedef double db;
- template<class T>
- void read(T &res) {
- res = 0;char c = getchar();T f = 1;
- while(c <'0' || c> '9') {
- if(c == '-') f = -1;
- c = getchar();
- }
- while(c>= '0' && c <= '9') {
- res = res * 10 + c - '0';
- c = getchar();
- }
- res *= f;
- }
- template<class T>
- void out(T x) {
- if(x <0) {x = -x;putchar('-');}
- if(x>= 10) {
- out(x / 10);
- }
- putchar('0' + x % 10);
- }
- const int MOD = 1004535809,MAXL = (1 <<14);
- int W[MAXL + 5],N,M,x,S;
- int pos[8005],pw[8005],f[MAXL + 5],r[MAXL + 5],tmp[MAXL + 5];
- int inc(int a,int b) {
- return a + b>= MOD ? a + b - MOD : a + b;
- }
- int fpow(int x,int c,int M = MOD) {
- int res = 1,t = x;
- while(c) {
- if(c & 1) res = 1LL * res * t % M;
- t = 1LL * t * t % M;
- c>>= 1;
- }
- return res;
- }
- int primitive_root(int p) {
- for(int g = 2 ; ; ++g) {
- bool flag = 1;
- for(int i = 2 ; i <= (p - 1) / i ; ++i) {
- if((p - 1) % i == 0) {
- if(fpow(g,(p - 1) / i,p) == 1 || fpow(g,i,p) == 1) {
- flag = 0;
- break;
- }
- }
- }
- if(flag) return g;
- }
- }
- void NTT(int *p,int L,int on) {
- for(int i = 1 , j = L>> 1 ; i <L - 1 ; ++i) {
- if(i < j) swap(p[i],p[j]);
- int k = L>> 1;
- while(j>= k) {
- j -= k;
- k>>= 1;
- }
- j += k;
- }
- for(int h = 2 ; h <= L ; h <<= 1) {
- int wn = W[(MAXL + on * MAXL / h) % MAXL];
- for(int k = 0 ; k <L ; k += h) {
- int w = 1;
- for(int j = k ; j < k + h / 2 ; ++j) {
- int u = p[j],t = 1LL * p[j + h / 2] * w % MOD;
- p[j] = inc(u,t);
- p[j + h / 2] = inc(u,MOD - t);
- w = 1LL * w * wn % MOD;
- }
- }
- }
- if(on == -1) {
- int InvL = fpow(L,MOD - 2);
- for(int i = 0 ; i < L ; ++i) p[i] = 1LL * p[i] * InvL % MOD;
- }
- }
- void Solve() {
- read(N);read(M);read(x);read(S);
- W[0] = 1;
- W[1] = fpow(3,(MOD - 1) / MAXL);
- for(int i = 2 ; i < MAXL ; ++i) {
- W[i] = 1LL * W[i - 1] * W[1] % MOD;
- }
- int t = primitive_root(M);
- pw[0] = 1;pw[1] = t;
- for(int i = 2 ; i < M ; ++i) pw[i] = 1LL * pw[i - 1] * pw[1] % M;
- for(int i = 0 ; i < M - 1 ; ++i) pos[pw[i]] = i;
- int k;
- for(int i = 1 ; i <= S ; ++i) {
- read(k);
- if(!k) continue;
- f[pos[k]] = 1;
- }
- k = 1;
- while(k <= 2 * M) k <<= 1;
- r[0] = 1;
- while(N) {
- NTT(f,k,1);
- if(N & 1) {
- NTT(r,k,1);
- for(int i = 0 ; i < k ; ++i) r[i] = 1LL * r[i] * f[i] % MOD;
- NTT(r,k,-1);
- for(int i = M - 1 ; i < k ; ++i) {r[i % (M - 1)] = inc(r[i % (M - 1)],r[i]);r[i] = 0;}
- }
- for(int i = 0 ; i < k ; ++i) f[i] = 1LL * f[i] * f[i] % MOD;
- NTT(f,k,-1);
- for(int i = M - 1 ; i < k ; ++i) {f[i % (M - 1)] = inc(f[i % (M - 1)],f[i]);f[i] = 0;}
- N>>= 1;
- }
- out(r[pos[x]]);enter;
- }
- int main() {
- #ifdef ivorysi
- freopen("f1.in","r",stdin);
- #endif
- Solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2874252.html