BZOJ_4818_[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取模。
Sample Input
3 5 3
Sample Output
33
求至少有一个质数的方案可以用总方案减去不含质数的方案。
先把1~m的质数筛出来，观察p特别小，考虑每个数%p的值对答案的贡献。
设F[i][j]表示从%p=i到%p=j的方案数，这个矩阵乘1次相当于向序列里多塞了个数，于是这道题变成了矩阵乘法。
然后发现f[i][j]=f[i+1][j+1],因此只需要对每个1~m中的i，f[0][i%p]++即可，剩下的可以通过平移得到。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
ll mod=20170408;
int n,m,p,prime[7000050],cnt;
bool vis[20000050];
struct Mat {
ll v[105][105];
Mat() {memset(v,0,sizeof(v));}
Mat operator*(const Mat a) const {
Mat ans;
int i,j,k;
for(i=1;i<=p;i++)
for(j=1;j<=p;j++)
for(k=1;k<=p;k++)
(ans.v[i][j]+=v[i][k]*a.v[k][j])%=mod;
return ans;
}
}A,B;
Mat pow(Mat x,int y) {
Mat I;
int i;
for(i=1;i<=p;i++) I.v[i][i]=1;
while(y) {
if(y&1) I=I*x;
x=x*x;
y>>=1;
}
return I;
}
void init() {
register int i,j;
vis[1]=1;
for(i=2;i<=m;i++) {
if(!vis[i]) {
prime[++cnt]=i;
}
for(j=1;j<=cnt&&i*prime[j]<=m;j++) {
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
int main() {
int i,j;
scanf("%d%d%d",&n,&m,&p);
init();
for(i=1;i<=m;i++) {
A.v[p][(i-1)%p+1]++;
if(vis[i]) B.v[p][(i-1)%p+1]++;
}
for(i=p-1;i;i--) {
for(j=1;j<=p;j++) {
A.v[i][j]=A.v[i+1][j%p+1];
B.v[i][j]=B.v[i+1][j%p+1];
}
}
printf("%lld
",(pow(A,n).v[p][p]-pow(B,n).v[p][p]+mod)%mod);
}