BZOJ 4818 SDOI2017 序列计数
2018-06-17 22:50:45来源：未知 阅读 ()
刚出炉的省选题，还是山东的。
自古山东出数学和网络流，堪称思维的殿堂，比某地数据结构成风好多了。
废话不说上题解。
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太大，然后我们发现这个转移重复了很多次，于是可以通过预处理贡献优化到p^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了！
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
下一篇：图论3 二分图匹配
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
- BZOJ1008: [HNOI2008]越狱(快速幂) 2019-08-26
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
