【bzoj4818】 Sdoi2017

http://www.lydsy.com/JudgeOnline/problem.php?id=4818 (题目链接)

题意

　　一个长度为$n$的序列，每个元素是不超过$m$的正整数，且这$n$个数的和是$p$的倍数，这$n$个数中至少有一个是质数，问这样的序列有多少个。

Solution

　　md吓死我了，还以为想错了，$p^2\log n$的半天不敢写=。=

　　$f[i][j]$表示忽略质数条件下的长度为$i$，和$mod~p=j$的序列数；$g[i][j]$表示满足没有一个数是质数的情况下长度为$i$，和$mod~p=j$的序列数。

　　然后这个东西倍增优化一下，每次$p^2$爆乘就好了。

细节

　　循环卷积。mdzz卡空间，明明原题空间是256M。。

代码

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define inf (1ll<<30)

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=10000010,maxm=1010,MOD=20170408;

int p[maxn];

bool vis[maxn<<1];

LL F[maxm],G[maxm],f[maxm],g[maxm],c[maxm];

int n,m,P;

void NTT(LL *a,LL *b,LL *r) {

	int N=P<<1;

	for (int i=0;i<N;i++) c[i]=0;

	for (int i=0;i<P;i++)

		for (int j=0;j<P;j++) (c[i+j]+=a[i]*b[j]%MOD)%=MOD;

	for (int i=0;i<P;i++) r[i]=(c[i]+c[i+P])%MOD;

}

int main() {

	scanf("%d%d%d",&n,&m,&P);

	vis[1]=1;

	for (int i=2;i<=m;i++) {

		if (!vis[i]) p[++p[0]]=i;

		for (int j=1;j<=p[0] && i*p[j]<=m;j++) {

			vis[i*p[j]]=1;

			if (i%p[j]==0) break;

		}

	}

	for (int i=1;i<=m;i++) {

		(++f[i%P])%=MOD;

		if (vis[i]) (++g[i%P])%=MOD;

	}

	F[0]=G[0]=1;

	for (;n;n>>=1) {

		if (n&1) NTT(F,f,F),NTT(G,g,G);

		NTT(f,f,f),NTT(g,g,g);

	}

	printf("%lld",(F[0]-G[0]+MOD)%MOD);

	return 0;

}

巴特西

【bzoj4818】 Sdoi2017—序列计数

题意

Solution

细节

代码

最新文章

热门文章