BZOJ 3992 序列统计

Description

Input

Output

Sample Input

Sample Output

这题让我知道了原根有什么用。

由于\(M\)是质数，所以\(M\)一定有原根\(G\)。我们只要知道\(1 \sim M-1\)在\(mod \; M\)意义下\(G\)的离散对数就可以把乘法化成了加法。

有了这个之后，我们就可以得到一个生成多项式。观察模数\(1004535809 = 2^{21} \times 479+1\)，所以可以使用NTT（快速数论变换，就是把FFT的单位复根变成\(1004535809\)的原根）+快速幂。（把这个题目告诉rhl，rhl直接秒，我太弱了TAT）

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

using namespace std;

#define gg (3)

#define rhl (1004535809)

#define maxm (16010)

typedef long long ll;

int n,m,x,S,G,tot,factor[maxm],pos[maxm],e[25],ine[25];

inline ll qsm(ll a,ll b,int c)

{

	ll ret = 1;

	for (;b;b >>= 1,(a *= a) %= c) if (b & 1) (ret *= a) %= c;

	return ret;

}

struct node

{

	int a[maxm*2],len;

	inline node() { memset(a,0,sizeof(a)); }

	inline void NTT(int loglen,int len,int on)

	{

		for (int i = 0,j,t,p;i < len;++i)

		{

			for (j = 0,t = i,p = 0;j < loglen;++j,t >>= 1) p <<= 1,p |= t & 1;

			if (p < i) swap(a[p],a[i]);

		}

		for (int s = 1,k = 2;s <= loglen;++s,k <<= 1)

		{

			int wn; if (on) wn = e[s]; else wn = ine[s];

			for (int i = 0;i < len;i += k)

			{

				int w = 1;

				for (int j = 0;j < (k >> 1);++j,w = (ll)wn*w%rhl)

					{

						int u = a[i+j],v = (ll)w*a[i+j+(k>>1)]%rhl;

						a[i+j] = u+v; if (a[i+j] >= rhl) a[i+j] -= rhl;

						a[i+j+(k>>1)] = u-v; if (a[i+j+(k>>1)] < 0) a[i+j+(k>>1)] += rhl;

					}

			}

		}

		if (!on)

		{

			int inv = qsm(len,rhl-2,rhl);

			for (int i = 0;i < len;++i) a[i] = (ll)a[i]*inv%rhl;

		}

	}

	friend inline node operator *(node x,node y)

	{

		int loglen = 0,len;

		for (;(1<<loglen)<x.len+y.len;++loglen); len = 1<<loglen;

		x.NTT(loglen,len,1); y.NTT(loglen,len,1);

		for (int i = 0;i < (1<<loglen);++i) x.a[i] = (ll)x.a[i]*y.a[i]%rhl;

		x.NTT(loglen,len,0);

		while (len&&(len >= m||!x.a[len-1]))

		{

			x.a[(len-1)%(m-1)] += x.a[len-1],x.a[--len] = 0;

			if (x.a[len%(m-1)] >= rhl) x.a[len%(m-1)] -= rhl;

		}

		x.len = len;

		return x;

	}

}pa;

inline bool check(int g)

{

	for (int i = 1;i <= tot;++i) if (qsm(g,(m-1)/factor[i],m) == 1) return false;

	return true;

}

int main()

{

	freopen("3992.in","r",stdin);

	freopen("3992.out","w",stdout);

	scanf("%d %d %d %d",&n,&m,&x,&S);

	for (int i = 2,p = m-1;p > 1;++i)

		if (!(p % i))

		{

			factor[++tot] = i;

			while (!(p % i)) p /= i;

		}

	for (int i = 1;i < m;++i) if (check(i)) { G = i; break; }

	for (int i = 0,now = 1;i < m-1;++i,(now *= G)%=m) pos[now] = i;

	for (int i = 1;i < 20;++i) e[i] = qsm(gg,(rhl-1)>>i,rhl),ine[i] = qsm(e[i],rhl-2,rhl);

	for (int i = 1,a;i <= S;++i) { scanf("%d",&a); if (a) pa.a[pos[a]]++; } pa.len = m-1;

	node ans; ans.a[0] = 1; ans.len = 1;

	for (;n;n >>= 1,pa = pa*pa)

		if (n & 1) ans = ans*pa;

	printf("%d",ans.a[pos[x]]);

	fclose(stdin); fclose(stdout);

	return 0;

}