Bzoj4818--Sdoi2017序列计数

Description

Alice想要得到一个长度为n的序列，序列中的数都是不超过m的正整数，而且这n个数的和是p的倍数。Alice还希望 ，这n个数中，至少有一个数是质数。Alice想知道，有多少个序列满足她的要求。

Input

一行三个数，n,m,p。 1<=n<=10^9,1<=m<=2×10^7,1<=p<=100

Output

一行一个数，满足Alice的要求的序列数量，答案对20170408取模。 ---------------------------------------------------------------此后一千里------------------------------------------------------------------------- 题解 ： 你问这题难不难？我就明确告诉你，不难。你问那我为什么要写题解？我就明确告诉你，因为我傻叉去写了矩阵快素幂。 ---ihopenot 题解基本已经在前面的引言里了。算出所有合法方案减去没有质数的方案。 然后我就随手一发矩阵快速幂。。。快速幂。。。幂。。。 然而这题用倍增去做每次只用p^2乘起来就可以了。复杂度直接少个p。。。 虽然矩阵也能过。 代码 ：（bzoj 18s） //That's right ,I am killer . #include<bits/stdc++.h> #define LL long long #define eps 1e-9 #define INF 0x3f3f3f3f using namespace std;#define int int inline int Max(int a,int b) {return a>b?a:b;} inline int Min(int a,int b) {return a<b?a:b;} inline int Sqr(int a) {return a*a;} inline int Abs(int a) {return a>0?a:-a;} #undef int#define MAXN 20000007 #define MOD 20170408int n,m,p;struct Matrix{int x[105][105];void Init() {memset(x,0,sizeof(x));}void Out() {for(int i=0;i<p;i++) {for(int j=0;j<p;j++) cout<<x[i][j]<<" ";cout<<endl;}}Matrix operator * (const Matrix &b) const {Matrix ret;ret.Init();for(int i=0;i<p;i++) for(int j=0;j<p;j++)for(int k=0;k<p;k++) ret.x[i][k]=(ret.x[i][k]+(LL) x[i][j]*b.x[j][k])%MOD;return ret;} }st,tra[2],e;Matrix Fpow(Matrix a,int p) {Matrix ret=e,tmp=a;while(p) {if(p&1) ret=ret*tmp;tmp=tmp*tmp; p>>=1;}return ret; }int pri[MAXN],cnt;bool mk[MAXN]; int ap[2][105]; void Pre() { st.x[0][0]=1;for(int i=0;i<p;i++) e.x[i][i]=1;mk[1]=1;for(int i=2;i<=m;i++) {if(!mk[i]) pri[++cnt]=i;for(int j=1;j<=cnt&&i*pri[j]<=m;j++) {mk[i*pri[j]]=1;if(i%pri[j]==0) break;}}for(int i=1;i<=m;i++) {ap[0][i%p]++;ap[1][i%p]+=mk[i] ? 1:0;}for(int k=0;k<p;k++) for(int i=0;i<p;i++) {tra[0].x[(i+k)%p][i]+=ap[0][k];tra[1].x[(i+k)%p][i]+=ap[1][k];} }int ans;int main() {scanf("%d%d%d",&n,&m,&p);Pre();tra[0]=Fpow(tra[0],n)*st;tra[1]=Fpow(tra[1],n)*st;ans=tra[0].x[0][0]-tra[1].x[0][0];ans=(ans+MOD)%MOD;printf("%d\n",ans);return 0; } View Code

 

转载于:https://www.cnblogs.com/ihopenot/p/6707542.html

总结

以上是生活随笔为你收集整理的Bzoj4818--Sdoi2017序列计数的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。