题目:
传送门
思路:
我们可以先写出转移方程,发现该方程是一个不变的递推式,我们考虑用矩阵快速幂来优化这个递推式.
完结撒花…
AC_Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const long long mod = 1e9+7;
long long n,UP;
struct mat
{
long long mn[9][9];
mat() {
for(int i = 0;i<UP;i++) {
for(int j = 0;j<UP;j++) {
mn[i][j]=0;
}
}
for(int i = 0;i<UP;i++) {
mn[i][i] = 1;
}
}
mat operator * (const mat& a) {
mat res;
for(int i = 0;i<UP;i++) {
res.mn[i][i] = 0;
}
for(int i=0;i<UP;i++) {
for(int j=0;j<UP;j++) {
for(int k=0;k<UP;k++) {
res.mn[i][j] += mn[i][k]*a.mn[k][j]%mod;
res.mn[i][j] %= mod;
}
}
}
return res;
}
};
mat fast(mat a,long long c) {
mat res = mat();
while(c) {
if(c&1) res = res * a;
a = a*a;
c >>= 1;
}
return res;
}
mat ans;
mat res;
int main() {
UP = 9;
scanf("%lld",&n);
for(int i = 0;i<9;i++) for(int j =0;j<9;j++) res.mn[i][j] = ans.mn[i][j] = 0;
for(int i = 0;i<3;i++) {
for(int j = 0;j<3;j++) {
for(int k = 0;k<3;k++) {
if(k*j<=i*i) res.mn[k*3+i][i*3+j] = 1;
}
}
}
for(int i = 0;i<9;i++) ans.mn[0][i] = 1;
res = fast(res,n-2);
ans = ans * res;
long long sum =0;
for(int i=0;i<9;i++) sum += ans.mn[0][i],sum%=mod;
printf("%lld\n",sum);
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)