洛谷题解 P3702 【[SDOI2017]序列计数

less than 1 minute read

Published:

快速幂

首先，考虑最简单的dp，用dp[k][i][j]表示当前枚举到第i位，当前数之和为j，k表示是否选择了质数，滚动数组滚掉i位，但是实际的复杂度为O(nm),能过多少分题面给的不清晰，反正至少能得到20分的好分数。

显然，这种是完全过不了的。但是当我们深入分析这个转移的实质，就会发现在每次往后一位转移的时候，转移是固定的，而我们用dp转移的时候会有大部分的重复，就显得很劣。

那么我们来重新考虑一下这个转移。(先不考虑质数的问题) 我们用f[i][j]表示在第i位选数和为j(在%p意义下的)，你会发现我这个和dp定义的没有什么区别。没错，我就是在废话。 对于最基础的转移，就是，$f[i+1][j]= \sum_{(k+l)\%p==j} f[k]+1 $ ,推广一下就是$f[i1+i2][j]+= \sum_{(k+l)\%p==j}f[i1][k]* f[i2][l]$ (定义为$ f[i1]*f[i2] $)。（记得mod 20170408） 对于这样一个式子，我们相当于$f[i1]$,$f[i2]$，我们相当于重新定义了他们的乘法法则，那么我们就可以对他进行快速幂。 现在我们唯一的问题就是在于出现质数怎么办，其实很简单，我们定义$f$为取全部数的情况，$g$为只出现非质数的情况，那么对于最后的答案我们是不是用$f-g$就是的答案了。(因为最终和为$p$，那么答案记录在$f[0]-g[0]$中)。时间复杂度$ O(p^2logn)$，完全能通过此题。

#include<bits/stdc++.h>
#define inf 999999999
#define dl double
#define ll long long
#define re register
#define V inline void
#define LL inline ll
#define I inline int
#define B inline bool
#define FOR(i,a,b) for(re int i=(a) ,i##i=(b) ; i<=i##i ; ++i)
#define AFOR(i,a,b) for(re int i=(a) , i##i=(b) ; i>=i##i ; --i)
#define REP(i,u) for(re int i=head[u],v=edge[i].to;i!=-1;i=edge[i].nxt,v=edge[i].to)
#define gc (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin),fs==ft))?0:*fs++
// #define gc getchar()
using namespace std;
const int N=2e7+10,mo=20170408;
char buf[1<<18],*fs,*ft;
inline ll read() {
	ll w=0,p=0;
	char ch=gc;
	while(!isdigit(ch)) w=ch=='-'?1:0,ch=gc;
	while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
	return w?-p:p;
}
inline void write(ll x) {
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
	return ;
}
int p,cnt,vis[N],pre[N];
ll n,m,f[300],g[300],F[300],G[300],c[300];
V mul(ll *a,ll *b){
	FOR(i,0,p-1) FOR(j,0,p-1) c[i+j]=(c[i+j]+a[i]*b[j])%mo;
	FOR(i,0,p-1) a[i]=(c[i]+c[i+p])%mo,c[i]=c[i+p]=0;
	return ;
}
int main(){
	n=read(),m=read(),p=read();
	f[1]=g[1]=F[0]=G[0]=1;
	FOR(i,2,m){
		++f[i%p];
		if(!vis[i]) pre[++cnt]=i;
		else ++g[i%p];
		FOR(j,1,cnt){
			if(i*pre[j]>m) break;
			vis[i*pre[j]]=1;
			if(i%pre[j]==0) break;
		}
	}
	while(n){
		if(n&1) mul(F,f),mul(G,g);
		mul(f,f),mul(g,g),n>>=1;
	}
	write((F[0]-G[0]+mo)%mo);
	return 0;
}

You May Also Enjoy