洛谷P3321 [SDOI2015]序列统计【NTT+原根】

题目描述

小C有一个集合 S,里面的元素都是小于 m 的非负整数。他用程序编写了一个数列生成器,可以生成一个长度为 n 的数列,数列中的每个数都属于集合 S。

小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助:给定整数 x,求所有可以生成出的,且满足数列中所有数的乘积mod m的值等于 x 的不同的数列的有多少个。

小C认为,两个数列 A 和 B 不同,当且仅当 ∃ i  s.t.  A i ≠ B i \exists i \text{ s.t. } A_i \neq B_i ∃i s.t. Ai​​=Bi​。另外,小C认为这个问题的答案可能很大,因此他只需要你帮助他求出答案对 1004535809取模的值就可以了。

输入格式

一行,四个整数n,m,x,|S|,其中∣S∣为集合S中元素个数
第二行,∣S∣个整数,表示集合S中的所有元素

输出格式

一行一个整数表示答案

题目分析

首先从一些简单情况考虑

  • Q:给定一个集合S,从S中选取2个数组成数列(可以重复),使得数列为A的方案数

定义 F ( i ) F(i) F(i)表示S中数值 i i i的个数,那么有
a n s = ∑ j = 0 A F ( j ) F ( A − j ) ans=\sum_{j=0}^{A}F(j)F(A-j) ans=j=0∑A​F(j)F(A−j)

再变复杂一点

  • Q:给定一个集合S,从S中选取n个数组成数列(可以重复),使得数列为A的方案数

令 F k ( i ) F_k(i) Fk​(i)表示从S中取 2 k 2^k 2k个数使得数列和为 i i i的方案数,那么显然有递推关系
F k ( i ) = ∑ j = 0 i F k − 1 ( j ) F k − 1 ( i − j ) F_k(i)=\sum_{j=0}^iF_{k-1}(j)F_{k-1}(i-j) Fk​(i)=j=0∑i​Fk−1​(j)Fk−1​(i−j)

然后将n二进制分解,设n的二进制中为1的位为 d 1 , d 2 , . . . , d c d_1,d_2,...,d_c d1​,d2​,...,dc​
则多项式 F d 1 , F d 2 , . . . , F d c F_{d_1},F_{d_2},...,F_{d_c} Fd1​​,Fd2​​,...,Fdc​​的乘积中A次项系数即为答案

  • Q:给定一个集合S,从S中选取n个数组成数列(可以重复),使得数列和mod m为A的方案数

思路同上一问,但每次计算多项式乘法后,将次数大于m的项按次数膜m累加到对应低次项

  • Q:给定一个集合S,从S中选取n个数组成数列(可以重复),使得数列乘积mod m(m为素数)为A的方案数

到这里就和原题询问一致了
只要把乘法化为加法就能用上一问的思路,而乘法化加法容易想到对数函数
但普通的对数函数无法在膜意义下计算,于是考虑原根和指标函数

g为模m的原根,则有 g 0 , g 1 , . . . , g φ ( m ) − 1 g^0,g^1,...,g^{\varphi(m)-1} g0,g1,...,gφ(m)−1在膜m意义下互不相同
定义指标函数 I ( x ) I(x) I(x)满足 g I ( x ) ≡ x ( m o d m ) g^{I(x)}\equiv x \pmod m gI(x)≡x(modm),也即 I ( g x m o d    m ) = x I(g^x \mod m)=x I(gxmodm)=x

详见原根的求解及应用

利用指标函数对集合S的数做映射后,即可利用前述方法解决该问题

#include<iostream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long lt;

int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

const lt P=1004535809,Grt=3,Ginv=334845270;
const int maxn=500010;
int fac[maxn],facN;
int mp[maxn];
lt F[maxn];
int lim,L,rev[maxn];
lt ans[maxn];

lt qpow(lt a,lt k,lt mod)
{
	lt res=1;
	while(k){
		if(k&1) res=(res*a)%mod;
		a=(a*a)%mod; k>>=1;
	}
	return res;
}

void NTT(lt *a,int opt)
{
	for(int i=0;i<lim;++i)
	if(i<rev[i]) swap(a[i],a[rev[i]]);
	
	for(int i=1;i<lim;i<<=1)
	{
		lt gn=qpow(opt==1?Grt:Ginv, (P-1)/(i<<1), P);
		for(int j=0;j<lim;j+=(i<<1))
		{
			lt g=1;
			for(int k=0;k<i;++k)
			{
				lt nx=a[j+k],ny=g*a[i+j+k]%P;
				a[j+k]=(nx+ny)%P;
				a[i+j+k]=(nx-ny+P)%P;
				g=g*gn%P;
			}
		}
	}
	
	lt inv=qpow(lim,P-2,P);
	if(opt==-1)
	{
		for(int i=0;i<lim;++i)
		a[i]=a[i]*inv%P;
	}
}

int qPhi(int x) // 求phi函数
{
    int res=x;
    for(int i=2;i*i<=x;++i)
    {
        if(x%i==0)
        {
            res=res/i*(i-1);
            while(x%i==0) x/=i;
        }
    }
    if(x>1) res=res/x*(x-1);
    return res;
}

void div(int x) // 分解质因数
{
	facN=0;
	for(int i=2;i*i<=x;++i)
	{
		if(x%i==0)
		{
			while(x%i==0) x/=i;
			fac[++facN]=i;
		}
	}
	if(x>1) fac[++facN]=x;
}

bool check(int g,int m,int phi)
{
	if(qpow(g,phi,m)!=1) return 0;
	
	for(int i=1;i<=facN;++i){
		if(qpow(g,phi/fac[i],m)==1) return 0;
	}
	
	return 1;
}

int minRt(int m)  // 求最小原根
{
	int phi=qPhi(m);
	div(phi);
	
	for(int i=1;i<=m;++i)
	if(check(i,m,phi)) return i;
	
	return 0;
}

void polyMul(lt *A,lt *B,int n1,int n2,lt *res,int m) // 多项式乘法
{
	static lt a[maxn],b[maxn];
	
	lim=1; L=0;
	while(lim<=n1+n2) lim<<=1,L++;
	for(int i=0;i<lim;++i)
	rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1));
	
	for(int i=0;i<lim;++i){ // 用临时数组运算
		a[i]=A[i]; b[i]=B[i];
	}
	
	NTT(a,1); NTT(b,1);
	for(int i=0;i<lim;++i)
	a[i]=a[i]*b[i]%P;
	
	NTT(a,-1);
	
	for(int i=0;i<m-1;++i) // 膜意义下
	res[i]=(a[i]+a[i+m-1])%P;
}

int main()
{
	int n=read(),m=read();
	int x=read(),S=read();
	
	int g=minRt(m);
	
	for(int i=0;i<m-1;++i) // 指标函数映射关系
	mp[qpow(g,i,m)]=i;
	
	for(int i=1;i<=S;++i)
	{
		int val=read()%m;
		if(val) F[mp[val]]++;
	}

	ans[0]=1;
	for(int i=0;(1<<i)<=n;++i)
	{
		if(n&(1<<i)) polyMul(ans,F,m-2,m-2,ans,m);
		polyMul(F,F,m-2,m-2,F,m);
	}
	
	printf("%lld",ans[mp[x]]);
	return 0;
}
上一篇:log4j2.xml


下一篇:Android性能优化 _ 大图做帧动画卡?优化帧动画之 SurfaceView滑动窗口式帧复用