sdoi<序列计数>

链接：https://www.luogu.org/problemnew/show/P3702

题解：

碰到计数题都要想想容斥

就跟碰到最大值最小要想想二分一样

考虑没有一个数是质数

那就确定了每一个数的取值范围

那么dp方程很显然

然后构造矩阵来优化转移

可以发现每个决策时一样的 所以矩阵可以一列一列的复制

#include <bits/stdc++.h>
#pragma comment(linker,"/STACK:102400000,102400000")
#pragma G++ optimize (“O2”) 
using namespace std;
#define ll long long
const ll maxn= 2e7+100;
#define mo 20170408
ll k,n,m;
bool f[maxn+10];
struct re{
    ll jz1[110][110],jz2[110][110];
}a;
re tmp,c;
re XX(re x,re y)
{
    memset(tmp.jz1,0,sizeof(tmp.jz1));
    memset(tmp.jz2,0,sizeof(tmp.jz2));
    for (ll i=0;i<k;i++)
      for (ll j=0;j<k;j++)
        for (ll p=0;p<k;p++)
        {
           tmp.jz1[i][p]=(tmp.jz1[i][p]+x.jz1[i][j]*y.jz1[j][p])%mo;
           tmp.jz2[i][p]=(tmp.jz2[i][p]+x.jz2[i][j]*y.jz2[j][p])%mo;    
        }
    return(tmp);
}
re fastpow(ll x)
{
    cout<<x<<endl;
    if (x==1) return(a);
    c=fastpow(x/2);
    c=XX(c,c);
    if (x%2) c=XX(c,a);
    return c;
}
int main()
{
    freopen("noip.in","r",stdin);
    freopen("noip.out","w",stdout); 
    cin>>n>>m>>k;
    memset(f,1,sizeof(f));
    f[0]=f[1]=0;
    for (ll i=2;i<=maxn;i++)
      if (f[i])
      {
          ll j=2;
          while (j*i<=maxn)
          {
              f[j*i]=0; j++;
        }
      }
    for (ll i=1;i<=m;i++)
      if (!f[i])
      {
          a.jz1[((-i%k)+k)%k][0]++;
      }
    for (ll i=1;i<k;i++)
    {
        for (ll j=1;j<k;j++)
          a.jz1[j][i]=a.jz1[j-1][i-1];
        a.jz1[0][i]=a.jz1[k-1][i-1];
    }
    for (ll i=1;i<=m;i++)
      a.jz2[((-i%k)+k)%k][0]++;
    for (ll i=1;i<k;i++)
    {
        for (ll j=1;j<k;j++)
          a.jz2[j][i]=a.jz2[j-1][i-1];
        a.jz2[0][i]=a.jz2[k-1][i-1];
    }
    re d=fastpow(n);
    cout<<(d.jz2[0][0]-d.jz1[0][0]+mo)%mo;
    return 0;
}