题解 P2359 【三素数数】

dspr · 2018-03-29 10:37:17 · 题解

对于一般dp解法下面都有，我这里就不再赘述。 然后我们会发现每一遍dp转移都是一样的，然后转移次数也是一定的，这时我们会想到什么，没错就是矩阵，根据素数判断构造出一个转移矩阵，跑一遍矩阵快速幂，可以跑过n=10^9的数据(建议出个数据加强版)。

update:无意中看到自己的题解，发现以前写的代码实在丑陋，忍受不了，于是改了一下

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int M=1e9+9,_=101;
struct matrix{
    ll a[_][_];
    matrix operator *(matrix b){
        matrix c;
        for(int i=1;i<=99;++i)
            for(int j=1;j<=99;++j){
                c.a[i][j]=0;
                for(int k=1;k<=99;++k)
                    c.a[i][j]+=a[i][k]*b.a[k][j]%M;
                c.a[i][j]%=M;
            }
        return c;
    }
}b;
ll a[_*10],c[_],n;
matrix js(matrix x,matrix y){
    matrix z;
    for(int i=1;i<=99;++i)
        for(int j=1;j<=99;++j){
            z.a[i][j]=0;
            for(int k=1;k<=99;++k)
                z.a[i][j]=(z.a[i][j]+x.a[i][k]*y.a[k][j])%M;
        }
    return z;
}
int main(){
    cin>>n;n-=3;
    int tt=0;
    for(int i=2;i<=1000;++i)
        for(int j=i+i;j<=1000;j+=i)
            a[j]=1;
    for(int i=100;i<=999;++i)
        if(!a[i]){
            tt++;
            c[i/10]++;
            b.a[i%100][i/10]++;
        }
    if(n==0){cout<<tt;return 0;}
    matrix ans=b;n--;
    while(n){
        if(n&1)ans=ans*b;
        b=b*b;
        n/=2;
    }
    ll t=0;
    for(int i=1;i<=99;++i)
        for(int j=1;j<=99;++j){
            t+=ans.a[i][j]*c[i];
            t%=M;
        }
    cout<<t<<endl;
    return 0;

}