题目
做法
这都没想到
首先，我们需要考虑有质数的，和没质数的情况。
但是我们发现，有质数的情况不可能用来推导没质数的情况，且总情况减去没有质数的情况就是有质数的情况，且有质数的情况需要用没质数的情况推导而成。
所以直接用处理无质数的情况和总情况（事实上，总情况总比无质数情况好处理，而无质数情况比有质数情况好处理），然后容斥求得即可，以此减少思考难度以及思考总量（事实上，用容斥一般可以减少常数甚至是复杂度，本题减少的是常数）。
现在说总情况的统计方法：
考虑DP，(f[i][j])，表示第(i)个位置和模(p)为(j)的情况个数，然后通过转移方程便可以得到，设(cnt_{i})为不超过(m)的且模(p)等于(i)的正整数个数，即：(f[i+1][(k+j)\%p]+=f[i][j]*cnt_k)，不难发现，这个转移可以写成矩阵的形式：
(egin{bmatrix}
cnt_0 &cnt_{p-1} & cnt_{p-2} & ...\
cnt_1 & cnt_0 & cnt_{p-1} & ...\
cnt_2 & cnt_1 & cnt_0 & ...\
... & ... & ... & ...
end{bmatrix})
把(f[i])看成(1*p)的矩阵，那么(f[i])转移到(f[i+1])就是乘这个矩阵。
直接矩阵快速幂加速即可。
至于没有质数的情况，一个很简单的方法就是把(cnt_{i})的定义加上不是质数。
如果你是在不想用容斥，也可以直接把DP设成(f[i][j][0/1])，分别表示有质数和没有质数，然后化成二维的(DP)：(f[i][j/j+p])，但是事实上非常的没有必要，因为矩阵长度乘二，相当于常数乘(8)，大概率过不了。
代码
时间复杂度：(O(p^3log{n}))
#include<cstdio>
#include<cstring>
#define N 21000000
#define SN 3100000
using namespace std;
typedef long long LL;
int li[SN],top;
bool v[N];
int n,m,p;
LL cn1[110],cn2[110];
LL mod=20170408;
void XXS()
{
cn1[1]=cn2[1]=1;
for(int i=2;i<=m;i++)
{
cn1[i%p]++;
if(!v[i])li[++top]=i;
else cn2[i%p]++;
for(int j=1;j<=top && i*li[j]<=m;j++)
{
v[li[j]*i]=1;
if(i%li[j]==0)break;
}
}
}
struct node
{
LL a[110][110];
node(){memset(a,0,sizeof(a));}
};
inline node operator*(node x,node y)
{
node z;
for(int i=0;i<p;i++)
{
for(int j=0;j<p;j++)
{
for(int k=0;k<p;k++)z.a[i][j]+=x.a[i][k]*y.a[k][j]%mod,z.a[i][j]%=mod;
}
}
return z;
}
inline node ksm(node x,int y)
{
node ans;
for(int i=0;i<p;i++)ans.a[i][i]=1;
while(y)
{
if(y&1)ans=ans*x;
x=x*x;y>>=1;
}
return ans;
}
int main()
{
scanf("%d%d%d",&n,&m,&p);
XXS();
LL ans=0;node x;
for(int i=0;i<p;i++)
{
for(int j=0;j<p;j++)x.a[i][(j+i)%p]=cn1[j];
}
x=ksm(x,n);
ans=x.a[0][0];
for(int i=0;i<p;i++)
{
for(int j=0;j<p;j++)x.a[i][(j+i)%p]=cn2[j];
}
x=ksm(x,n);
ans-=x.a[0][0];
ans=(ans+mod)%mod;
printf("%lld
",ans);
return 0;
}
小结
- 在思考的过程中，如果思考的两个部分（或者多个部分）之间，存在容斥，可以通过思考容斥减少情况，以此减少思考难度。（当然，思维要放开，有时候不一定要用容斥，但是在本题容斥一般比不容斥优秀）。
- 有时候一次性想不到正解的话，可以通过考虑时间较大的解法并进行优化，因为有的题目可能就是优化题。