自动搬运

查看原文

来自洛谷，原作者为

	dspr **

搬运于2025-08-24 21:36:46，当前版本为作者最后更新于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;

}