网页游戏网站那个好,郑州网站开发与建设,塘沽网红餐厅,房产网签合同平台正题
题目链接:https://jzoj.net/senior/#contest/show/3017/2 题目大意
求有多少个长度为nnn的序列使得
都是在集合SSS中的数这些数的乘积%mx\% mx%mx 解题思路
设fi,jf_{i,j}fi,j表示长度为iii的序列#xff0c;乘积为jjj的有多少个#xff0c;显然有 fi,j∗w%mfi−1…正题
题目链接:https://jzoj.net/senior/#contest/show/3017/2 题目大意
求有多少个长度为nnn的序列使得
都是在集合SSS中的数这些数的乘积%mx\% mx%mx 解题思路
设fi,jf_{i,j}fi,j表示长度为iii的序列乘积为jjj的有多少个显然有 fi,j∗w%mfi−1,j(w∈S)f_{i,j*w\%m}f_{i-1,j}(w\in S)fi,j∗w%mfi−1,j(w∈S) 然后有 f2∗i,j∑a∗b%mjfi,a∗fi,bf_{2*i,j}\sum_{a*b\%mj}f_{i,a}*f_{i,b}f2∗i,ja∗b%mj∑fi,a∗fi,b
此时我们可以用矩阵乘法做到O(m3logn)O(m^3\log n)O(m3logn)
但是此复杂度显然无法胜任本题
因为mmm是质数所以对于1∼m−11\sim m-11∼m−1都可以用一个gi%mg^i\% mgi%m表示出来我们枚举找出一个ggg后就有 fi,jf_{i,j}fi,j表示长度为iii的序列乘积为gj%mg_j\%mgj%m的有多少个 那么就有f2∗i,j∑(ab)%mjfi,a∗fi,bf_{2*i,j}\sum_{(ab)\%mj}f_{i,a}*f_{i,b}f2∗i,j(ab)%mj∑fi,a∗fi,b
这很显然是一个卷积的形式所以我们表示出一个多项式后用NTTNTTNTT做快速幂即可。
时间复杂度:O(mlogmlogn):O(m\log m\log n):O(mlogmlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N5e410,XJQ1004535809;
ll n,m,z,s,d[N],cnt,len,invn;
ll f[N],ans[N],tmp1[N],tmp2[N],r[N];
bool v[N];
ll power(ll x,ll b,ll p){ll ans1;while(b){if(b1)ansans*x%p;xx*x%p;b1;}return ans;
}
ll FindRoot(){ll lm-1;for(ll i2;i*il;i){if(l%i0){d[cnt]i;while(l%i0)l/i;}}if(l!1) d[cnt]l;lm-1;for(ll i2;il;i){bool flag1;for(ll j1;jcnt;j)if(power(i,l/d[j],m)1){flag0;break;}if(flag) return i;}return 0;
}
void NTT(ll *x,ll op){for(ll i0;ilen;i)if(ir[i])swap(x[i],x[r[i]]);for(ll p2;plen;p1){ll lp1,tmppower(3,(XJQ-1)/p,XJQ);if(op-1)tmppower(tmp,XJQ-2,XJQ);for(ll k0;klen;kp){ll buf1;for(ll ik;ikl;i){ll ttbuf*x[li]%XJQ;x[li](x[i]-ttXJQ)%XJQ;x[i](x[i]tt)%XJQ;bufbuf*tmp%XJQ;}}}if(op-1)for(int i0;ilen;i)x[i]x[i]*invn%XJQ;
}
void mul(ll *a,ll *b){for(ll i0;ilen;i)tmp1[i]a[i],tmp2[i]b[i];NTT(tmp1,1);NTT(tmp2,1);for(ll i0;ilen;i)tmp1[i]tmp1[i]*tmp2[i]%XJQ;NTT(tmp1,-1);for(ll i0;im-1;i)a[i](tmp1[i]tmp1[im-1])%XJQ;
}
int main()
{ll z0;scanf(%lld%lld%lld%lld,n,m,z0,s);ll rootFindRoot();for(ll i1;is;i){ll x;scanf(%lld,x);v[x]1;}for(ll i0,x1;im-1;i,xx*root%m){if(v[x])f[i]1;if(xz0)zi;}for(len1;len(m-1)1;len1);for(ll i0;ilen;i)r[i](r[i1]1)|((i1)?len1:0);ans[0]1;invnpower(len,XJQ-2,XJQ);while(n){if(n1)mul(ans,f);mul(f,f);n1;}printf(%lld,ans[z]);
}
