程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> bzoj3992【SDOI2015】序列統計

bzoj3992【SDOI2015】序列統計

編輯:關於C++

3992: [SDOI2015]序列統計

Time Limit:30 SecMemory Limit:128 MB
Submit:673Solved:327
[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中元素不重復

Source

Round 1 感謝yts1999上傳


NTT第一題

首先可以發現1004535809=479*2^21+1,而且是一個質數,所以可以用NTT解決。

用f[i][j]表示i個數模m等於g^j的方案數(i為2的整數次冪,g為m的原根),則f[i][j]=∑f[i/2][k]*f[i/2][j-k]。這樣就成了卷積形式,NTT搞定。但n並不一定是2的整數次冪,這裡就要用到快速冪的思想(詳見代碼)。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 40000
#define mod 1004535809
using namespace std;
int n,m,num,s,mg,g,bit,inv;
int a[maxn],c[maxn],A[maxn],B[maxn],ind[maxn],rev[maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline ll power(ll x,int y,int p)
{
	ll ret=1;
	for(;y;y>>=1,x=x*x%p) if (y&1) ret=ret*x%p;
	return ret;
}
inline bool get_order(int x,int m)
{
	int lim=sqrt(m),phi=m-1;
	F(i,1,lim) if (phi%i==0)
	{
		if (power(x,i,m)==1){if (i!=m-1) return false;}
		if (power(x,phi/i,m)==1){if (phi/i!=m-1) return false;}
	}
	return true;
}
inline int get_primitive_root(int x)
{
	F(i,2,x) if (get_order(i,x)) return i;
}
inline void ntt(int *a,int flag)
{
	F(i,0,(1<i) swap(a[i],a[rev[i]]);
	F(i,1,bit)
	{
		int y=(1ll*flag*(mod-1)/(1<>1]>>1|((i&1)<<(bit-1));
	A[0]=1;
	F(i,1,s) if (a[i]) B[ind[a[i]]]=1;
	for(;n;convol(B,B),n>>=1) if (n&1) convol(A,B);
	printf("%d\n",A[ind[num]]);
	return 0;
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved