泰州网站制作网站,我想网上开店怎么开,成都免费建站,wordpress卸载重装DP一下#xff0c;设$f_{i,j}$表示生成$i$个数且乘积$\%Mj$的方案数#xff0c;则$f_{i1,l}\sum\limits_{jk\%Ml}[k\in S]f_{i,j}$ 我们很不希望DP式中下标的位置出现乘法#xff0c;因为这样不好转移#xff0c;考虑把乘法换成加法 因为模数$M$是质数#xff0c;所以它有…DP一下设$f_{i,j}$表示生成$i$个数且乘积$\%Mj$的方案数则$f_{i1,l}\sum\limits_{jk\%Ml}[k\in S]f_{i,j}$ 我们很不希望DP式中下标的位置出现乘法因为这样不好转移考虑把乘法换成加法 因为模数$M$是质数所以它有原根于是对于每个$1\leq x\leq M-1$都有唯一的$0\leq x\leq M-2$使得$xg^{x}$所以DP式可以写成$f_{i1,g^{l}}\sum\limits_{g^{jk}\%Mg^{l}}[g^{k}\in S]f_{i,g^{j}}$令$h_{i,j}f_{i,g^j},S\{x|g^x\in S,0\leq x\leq M-2\}$则$h_{i1,l}\sum_{(jk)\%(M-1)l}\limits[k\in S]h_{i,j}$这是卷积的形式$jk\geq M-1$的项最后加到低次的项中所以我们可以用FFT做到在$O(n\log_2n)$的时间内从$h_i$转移到$h_{i1}$ $n$很大但是每次转移都是一样的所以只需要快速幂就好了总时间复杂度$O(M\log_2M\log_2n)$ 注意题目给的$S$中是有可能出现$0$的忽略就好 #includestdio.h
#includestring.h
const int mod1004535809;
typedef long long ll;
int mul(int a,int b,int pmod){return a*(ll)b%p;}
int ad(int a,int b){return(ab)%mod;}
int de(int a,int b){return(a-b)%mod;}
void swap(inta,intb){a^b^a^b;}
int rev[40010],N,iN,m;
int pow(int a,int b){int s1;while(b){if(b1)smul(s,a);amul(a,a);b1;}return s;
}
void pre(int n){int i,k;for(N1,k0;Nn;N1)k;for(i0;iN;i)rev[i](rev[i1]1)|((i1)(k-1));iNpow(N,mod-2);
}
void ntt(int*a,int on){int i,j,k,t,w,wn;for(i0;iN;i){if(irev[i])swap(a[i],a[rev[i]]);}for(i2;iN;i1){wnpow(3,(on1)?(mod-1)/i:(mod-1-(mod-1)/i));for(j0;jN;ji){w1;for(k0;ki1;k){tmul(w,a[i/2jk]);a[i/2jk]de(a[jk],t);a[jk]ad(a[jk],t);wmul(w,wn);}}}if(on-1){for(i0;iN;i)a[i]mul(a[i],iN);}
}
struct poly{int n,a[40010];poly(){n0;memset(a,0,sizeof(a));}
};
poly operator*(poly x,poly y){int i;poly c;pre(x.ny.n1);ntt(x.a,1);ntt(y.a,1);for(i0;iN;i)c.a[i]mul(x.a[i],y.a[i]);ntt(c.a,-1);for(im-1;iN;i){c.a[i%(m-1)]ad(c.a[i%(m-1)],c.a[i]);c.a[i]0;}c.nm-2;return c;
}
int getg(int p){int i,j,t;for(i2;ip;i){t1;for(j1;jp-1;j){tmul(t,i,p);if(t1)break;}if(jp-1)break;}return i;
}
int s[8010],r[8010];
poly pow(poly a,int b){poly s;s.a[0]1;while(b){if(b1)ss*a;aa*a;b1;}return s;
}
int main(){int n,x,ss,i,g,b;poly a;scanf(%d%d%d%d,n,m,x,ss);for(i1;iss;i)scanf(%d,si);ggetg(m);b1;for(i0;im-1;i){r[b]i;bmul(b,g,m);}for(i1;iss;i){if(s[i])a.a[r[s[i]]]1;}a.nm-2;while(a.a[a.n]0)a.n--;apow(a,n);printf(%d,(a.a[r[x]]mod)%mod);
}转载于:https://www.cnblogs.com/jefflyy/p/8717294.html
