注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3992][SDOI2015]序列统计  

2015-05-14 15:26:12|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3992: [SDOI2015]序列统计

Time Limit: 30 Sec  Memory Limit: 128 MB
Submit: 177  Solved: 101
[Submit][Status][Discuss]

Description

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

Input

一行,四个整数,N、M、x、|S|,其中|S|为集合S中元素个数。第二行,|S|个整数,表示集合S中的所有元素。

Output

一行,一个整数,表示你求出的种类数mod 1004535809的值。

Sample Input

4 3 1 2 1 2

Sample Output

8

HINT

【样例说明】
可以生成的满足要求的不同的数列有(1,1,1,1)、(1,1,2,2)、(1,2,1,2)、(1,2,2,1)、(2,1,1,2)、(2,1,2,1)、(2,2,1,1)、(2,2,2,2)。
【数据规模和约定】
对于10%的数据,1<=N<=1000;
对于30%的数据,3<=M<=100;
对于60%的数据,3<=M<=800;
对于全部的数据,1<=N<=109,3<=M<=8000,M为质数,1<=x<=M-1,输入数据保证集合S中元素不重复

Solution

把每个数取log的话,就把乘法变成加法了。
于是对质数m求原根,并求出每个数的离散对数,然后DP的转移实质上是一个多项式乘法,后面就是模板了。

Code

/**************************************************************
    Problem: 3992
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:3548 ms
    Memory:1332 kb
****************************************************************/
 
#include<cstdio>
int aa;char ch;int F(){
    while(ch=getchar(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getchar(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
typedef long long ll;
const int N=16666,P=479<<21|1;
int k,n,l,X,p,i,j,f[N],t[N],w[2][N],ind[N],rev[N],pw[N],tmp,y[N];ll g,inn;
int power(ll t,int k,int P){ll f=1;
    for(;k;k>>=1,t=t*t%P)if(k&1)f=f*t%P;
    return f;
}
bool check(){
    for(i=2;i*i<=p;i++)
    if((p-1)%i==0&&power(g,(p-1)/i,p)==1)return 0;
    return 1;
}
void getroot(){
    if(p==2)g=1;else for(g=2;!check();g++);
    for(ind[1]=0,pw[0]=i=1;i<p-1;i++)pw[i]=pw[i-1]*g%p,ind[pw[i]]=i;
}
#define swap(a,b) (tmp=a,a=b,b=tmp)
#define ck(x) (x>=P?x-=P:1)
void FFT(int*a,int v){int i,j,k;
    for(i=0;i<n;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
    for(i=2;i<=n;i<<=1)
    for(j=0;j<n;j+=i)
    for(k=0;k<i>>1;k++)
    tmp=1LL*a[j+k+i/2]*w[v][n/i*k]%P,a[j+k+i/2]=a[j+k]-tmp+P,ck(a[j+k+i/2]),a[j+k]+=tmp,ck(a[j+k]);
    if(v)for(i=0;i<n;i++)a[i]=inn*a[i]%P;
}
void mul(int*a,int*b){
    for(int i=0;i<n;i++)y[i]=b[i];
    FFT(a,0),FFT(y,0);
    for(int i=0;i<n;i++)a[i]=1LL*a[i]*y[i]%P;
    FFT(a,1);
    for(int i=n-1;i>=p-1;i--)a[i-p+1]+=a[i],ck(a[i-p+1]),a[i]=0;
}
int main(){
    for(k=F(),p=F(),X=F(),getroot(),n=F();n--;)if(j=F())t[ind[j]]++;
    for(n=1;n<p;n<<=1,l++);n<<=1;inn=power(n,P-2,P);
    for(g=power(3,(P-1)/n,P),i=0,j=1;i<=n;i++,j=g*j%P)rev[i]=(rev[i>>1]>>1)|((i&1)<<l),w[1][n-i]=w[0][i]=j;
    for(f[0]=1;k;k>>=1,mul(t,t))if(k&1)mul(f,t);
    printf("%d\n",f[ind[X]]);
}
  评论这张
 
阅读(105)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018