首页 > 代码库 > 【BZOJ3992】【SDOI2015】序列统计

【BZOJ3992】【SDOI2015】序列统计

2024-09-19 10:47:40   218人阅读

数论劲啊

原题：

小C有一个集合S，里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为N的数列，数列中的每个数都属于集合S。
小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：给定整数x，求所有可以生成出的，且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。小C认为，两个数列{Ai}和{Bi}不同，当且仅当至少存在一个整数i，满足Ai≠Bi。另外，小C认为这个问题的答案可能很大，因此他只需要你帮助他求出答案mod 1004535809的值就可以了。
1<=N<=10^9，3<=M<=8000，M为质数，0<=x<=M-1，输入数据保证集合S中元素不重复

 

首先因为M是质数并且0<=x和S中的元素<=M-1，就说明M有原根而且能很快求出来

于是对于i∈[0,M-1]的数都可以表示成原根的ki(k∈[0,M-1])次幂形式而且k互补相同

于是乘法就转化成了幂的加法，问题变成给|S|个数，求选n个数使得这n个数的和膜M==x的方案数（一个数可以选多次

所以生成函数，对于每个集合中的数si的ki，用ai表示kj==i有多少个（实际上最多只有一个，因为ki互不相同，同时S中的数互不相同

那么最终生成的多项式就是A=a_0+a_1*x+a_2*x^2+……a_{m-1}*x^{m-1}

因为有n个物品，所以多项式卷积n次

因为给的模数是恩梯梯模数，所以使用NTT计算精确答案

最后的答案就是(A^n)的第k_{x}相

代码：

技术分享 
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 using namespace std;
 7 #define ll long long
 8 const ll mo=1004535809;
 9 int rd(){int z=0,mk=1;  char ch=getchar();
10     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)mk=-1;  ch=getchar();}
11     while(ch>=‘0‘&&ch<=‘9‘){z=(z<<3)+(z<<1)+ch-‘0‘;  ch=getchar();}
12     return z*mk;
13 }
14 int wtp=0,wtc[32];
15 void wt(int x,char y){
16     if(!x){  putchar(‘0‘);  return ;}
17     if(x<0)  putchar(‘-‘),x=-x;
18     while(x)  wtc[++wtp]=x%10+‘0‘,x/=10;
19     while(wtp)  putchar(wtc[wtp--]);
20     putchar(y);
21 }
22 ll n,m,t,s;  int g,tg[210000];
23 ll a[210000],b[210000],tmp[210000],_x,_y;
24 int rvs[210000],dg[32],N,L;  ll _1_N;
25 int stck[210000],tp=0;
26 ll qcp(ll x,int y,int p){
27     ll z=1,bs=x;
28     for(;y;y>>=1){
29         if(y&1)  z=(z*bs)%p;
30         bs=(bs*bs)%p;
31     }
32     return z;
33 }
34 int gtg(){
35     int _m=m-1;
36     for(int i=2;i<=_m;++i)if(!(_m%i)){
37         stck[++tp]=i;
38         while(!(_m%i))  _m/=i;
39     }
40     for(int i=2,mk=false;;++i,mk=false){
41         for(int j=1;j<=tp;++j)
42             if(qcp(i,(m-1)/stck[j],m)==1){
43                 mk=true;
44                 break;
45             }
46         if(!mk)  return i;
47     }
48 }
49 void ntt(ll x[],ll mk){
50     for(int i=0;i<N;++i)  tmp[i]=x[rvs[i]];
51     for(int i=0;i<N;++i)  x[i]=tmp[i];
52     for(int i=2;i<=N;i<<=1){
53         ll wn=qcp(3,(mk*((mo-1)/i))%(mo-1),mo);
54         for(int k=0;k<N;k+=i){
55             ll w=1;
56             for(int j=k;j<k+(i>>1);++j){
57                 _x=x[j],_y=(x[j+(i>>1)]*w)%mo;
58                 x[j]=(_x+_y)%mo,x[j+(i>>1)]=(_x-_y+mo)%mo;
59                 w=(w*wn)%mo;
60             }
61         }
62     }
63     if(mk==mo-2)  for(int i=0;i<N;++i)  x[i]=(x[i]*_1_N)%mo;
64 }
65 void cclt(){
66     b[0]=1;
67     for(;n;n>>=1){
68         ntt(a,1);
69         if(n&1){
70             ntt(b,1);  for(int i=0;i<N;++i)  b[i]=(b[i]*a[i])%mo;
71             ntt(b,mo-2);  for(int i=N-1;i>=m-1;--i)  b[i-m+1]=(b[i-m+1]+b[i])%mo,b[i]=0;
72         }
73         for(int i=0;i<N;++i)  a[i]=(a[i]*a[i])%mo;
74         ntt(a,mo-2);
75         for(int i=N-1;i>=m-1;--i)  a[i-m+1]=(a[i-m+1]+a[i])%mo,a[i]=0;
76     }
77 }
78 int main(){//freopen("ddd.in","r",stdin);
79     cin>>n>>m>>t>>s;
80     g=gtg();
81     for(int i=0,x=1;i<m-1;++i,x=(x*g)%m)  tg[x]=i;
82     int x;
83     for(int i=1;i<=s;++i){
84         x=rd();
85         if(x)  ++a[tg[x]];
86     }
87     for(N=1,L=0;N<=m;N<<=1,++L);  N<<=1,++L;
88     _1_N=qcp(N,mo-2,mo);
89     for(int i=0;i<N;++i){
90         for(int j=i,k=0;j;j>>=1,++k)  dg[k]=j&1;
91         for(int j=0;j<L;++j)  rvs[i]=(rvs[i]<<1)|dg[j];
92     }
93     cclt();
94     cout<<b[tg[t]]<<endl;
95     return 0;
96 }
View Code

 

【BZOJ3992】【SDOI2015】序列统计


联系
我们