BZOJ 4818 SDOI2017 序列計數，bzoj4818

BZOJ 4818 SDOI2017 序列計數，bzoj4818

剛出爐的省選題，還是山東的。

自古山東出數學和網絡流，堪稱思維的殿堂，比某地數據結構成風好多了。

廢話不說上題解。

1.題面

　　求：n個數(順序可更改)，值域為[1,m]，和為p的倍數，且這些樹裡面有質數的方案數是多少？

解題報告：

　　0% O(n^n)爆搜，沒什麼好講的，用來拍DP；

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const int N = 20000010;
int n,P[N],tot,m,k;
LL Ans,tim;
bool vis[N];
inline int gi()
{
	int x=0,res=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')res=-res;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
	return x*res;
}

inline void shai()
{
	vis[1]=1;
	for(int i=2;i<=m;++i)
		{
			if(!vis[i])P[++tot]=i;
			for(int j=1;j<=tot;++j)
				{
					if(i*P[j]>m)break;
					vis[i*P[j]]=true;
					if(i%P[j]==0)break;
				}
		}
}

inline void dfs(int dep,int flag,int sum)
{
	if(dep==n){if(flag==1&&(sum%k==0))Ans++;return;}
	for(int x=1;x<=m;++x)
		if(vis[x]==false)dfs(dep+1,1,sum+x);
		else dfs(dep+1,flag,sum+x);
}
int main()
{
	freopen("in.txt","r",stdin);
	freopen("BL.txt","w",stdout);
	n=gi();m=gi();k=gi();shai();
	dfs(0,0,0);cout<<Ans%20170408<<endl;
}

　　30% O(nmp)DP;

　　　　注意到每一個數可以任意取，就是很顯然的具有DP性質了。那麼有兩種DP方法：

　　　　　　1.f[i][j][0/1]表示第i個數，模p為j，有無質數的情況；這種我寫到一半停下來了，因為我發現了第二種DP可以優化。

　　　　　　2.f[i][j]和g[i][j]分別表示瞎幾把亂取數和不取質數的情況，求出後相減即可(容斥思想)。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const int N = 20000010;
const int Mod = 20170408;
int n,P[N],tot,m,p,f[10100][101];
LL Ans,tim;
bool vis[N];

inline int gi()
{
	int x=0,res=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')res=-res;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
	return x*res;
}

inline void shai()
{
	vis[1]=1;
	for(int i=2;i<=m;++i)
		{
			if(!vis[i])P[++tot]=i;
			for(int j=1;j<=tot;++j)
				{
					if(i*P[j]>m)break;
					vis[i*P[j]]=true;
					if(i%P[j]==0)break;
				}
		}
}

int main()
{
	freopen("in.txt","r",stdin);
	freopen("DP.txt","w",stdout);
	n=gi();m=gi();p=gi();shai();
	f[0][0]=1ll;
	for(int i=0;i<n;++i)
		for(int j=0;j<p;++j)
			for(int k=1;k<=m;++k)
				{
					f[i+1][(j+k)%p]+=f[i][j];
					if(f[i+1][(j+k)%p]>Mod)
						f[i+1][(j+k)%p]-=Mod;
				}
	Ans=(LL)f[n][0];
	memset(f,0,sizeof(f));f[0][0]=1ll;
	for(int i=0;i<n;++i)
		for(int j=0;j<p;++j)
			for(int k=1;k<=m;++k)
				{
					if(!vis[k])continue;
					f[i+1][(j+k)%p]+=f[i][j];
					if(f[i+1][(j+k)%p]>Mod)
						f[i+1][(j+k)%p]-=Mod;
				}
	Ans-=(LL)f[n][0];
	printf("%lld\n",(Ans%Mod+Mod)%Mod);
}

　　　80%：我們發現狀態轉移方程是一個第一維線性遞推，第二維穩定一階轉移。然後發現p只有100，於是就可以上矩陣快速冪。建立轉移矩陣就是上面的DP式子。復雜度O(mp+p^3logn)

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const int N = 20000010;
const int Mod = 20170408;
struct Matrix{
	int T[105][105];
}S0,M0,M1;
int n,P[N],tot,m,p;
LL Ans;
bool vis[N];

inline int gi()
{
	int x=0,res=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')res=-res;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
	return x*res;
}

inline void shai()
{
	vis[1]=1;
	for(int i=2;i<=m;++i)
		{
			if(!vis[i])P[++tot]=i;
			for(int j=1;j<=tot;++j)
				{
					if(i*P[j]>m)break;
					vis[i*P[j]]=true;
					if(i%P[j]==0)break;
				}
		}
}

inline Matrix Mul(Matrix a,Matrix b,int I,int K,int J)
{
	Matrix S=S0;
	for(int i=0;i<I;++i)
		for(int j=0;j<J;++j)
			for(int k=0;k<K;++k)
				S.T[i][j]=((LL)(S.T[i][j])+((LL)a.T[i][k]*(LL)b.T[k][j]%Mod))%Mod;
	return S;
}

inline Matrix Qpow(Matrix s,Matrix d,int z,int I,int K,int J)
{
	Matrix S=s;
	for(;z;z>>=1,d=Mul(d,d,I,K,J))
		if(z&1)S=Mul(S,d,I,K,J);
	return S;
}

int main()
{
	freopen("in.txt","r",stdin);
	freopen("MT.txt","w",stdout);
	n=gi();m=gi();p=gi();shai();
	M0.T[0][0]=1ll;
	for(int i=0;i<p;++i)
		for(int j=1;j<=m;++j)
			{
				M1.T[i][(i+j)%p]++;
				M1.T[i][(i+j)%p]%=Mod;
			}
	Matrix ans1 = Qpow(M0,M1,n,p,p,p);
	Ans+=ans1.T[0][0];M0=M1=S0;M0.T[0][0]=1ll;
	for(int i=0;i<p;++i)
		for(int j=1;j<=m;++j)
			{
				if(!vis[j])continue;
				M1.T[i][(i+j)%p]++;
				M1.T[i][(i+j)%p]%=Mod;
			}
	Matrix ans2 = Qpow(M0,M1,n,p,p,p);
	Ans-=ans2.T[0][0];
	printf("%lld\n",(Ans%Mod+Mod)%Mod);
}

　　　100%：我們發現時間TLE在於構建矩陣時的mp太大，然後我們發現這個轉移重復了很多次，於是可以通過預處理貢獻優化到m^2；　

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const int N = 20000010;
const int Mod = 20170408;
struct Matrix{
	int T[105][105];
}S0,M0_1,M1_1,M0_2,M1_2,ans;
int n,P[N],tot,m,p,foo[200];
LL Ans;
bool vis[N];

inline int gi()
{
	int x=0,res=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')res=-res;ch=getchar();}
	while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
	return x*res;
}

inline void shai()
{
	vis[1]=1;
	for(int i=2;i<=m;++i)
		{
			if(!vis[i])P[++tot]=i;
			for(int j=1;j<=tot;++j)
				{
					if(i*P[j]>m)break;
					vis[i*P[j]]=true;
					if(i%P[j]==0)break;
				}
		}
}

inline Matrix Mul(Matrix a,Matrix b,int I,int K,int J)
{
	Matrix S=S0;
	for(int i=0;i<I;++i)
		for(int j=0;j<J;++j)
			for(int k=0;k<K;++k)
				S.T[i][j]=(S.T[i][j]+(LL)a.T[i][k]*b.T[k][j])%Mod;
	return S;
}

inline Matrix Qpow(Matrix S,Matrix d,int z,int I,int K,int J)
{
	for(;z;z>>=1,d=Mul(d,d,I,K,J))
		if(z&1)S=Mul(S,d,I,K,J);
	return S;
}

int main()
{
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	n=gi();m=gi();p=gi();shai();
	M0_1.T[0][0]=M0_2.T[0][0]=1ll;
	for(int i=1;i<=m;++i)++foo[i%p];
	for(int i=0;i<p;++i)
		for(int j=0;j<p;++j)
			{
				int st=(i+j)%p;
				M1_1.T[i][st]+=foo[j];
				if(M1_1.T[i][st]>=Mod)
					M1_1.T[i][st]-=Mod;
			}
	ans = Qpow(M0_1,M1_1,n,p,p,p);
	Ans+=ans.T[0][0];
	for(int i=0;i<p;++i)foo[i]=0;
	for(int i=1;i<=m;++i)
		if(vis[i])++foo[i%p];
	for(int i=0;i<p;++i)
		for(int j=0;j<p;++j)
			{
				int st=(i+j)%p;
				M1_2.T[i][st]+=foo[j];
				if(M1_2.T[i][st]>=Mod)
					M1_2.T[i][st]-=Mod;
			}
	ans = Qpow(M0_2,M1_2,n,p,p,p);
	Ans-=ans.T[0][0];
	printf("%lld\n",(Ans%Mod+Mod)%Mod);
}

//然後你就華麗的AC了！