voj 1067 经典矩阵7 递推+矩阵快速幂
程序员文章站
2024-03-24 15:57:04
...
感觉网上其他题解有点奇怪
这个图写错了,矩阵写到前面去。
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll mod = 7777777;
const int maxn=11;
struct matrix{
ll arr[maxn][maxn];
matrix operator*(matrix b){
matrix ans;
ll tmp;
for(int i=0; i<maxn; i++)
for(int j=0; j<maxn; j++){
ans.arr[i][j] = 0;
for(int k=0; k<maxn; k++){
tmp = (arr[i][k]*b.arr[k][j])%mod;
ans.arr[i][j] = (ans.arr[i][j] + tmp)%mod;
}
}
return ans;
}
};
matrix quick_pow(matrix a,ll N){
matrix ans;
memset(ans.arr,0,sizeof(ans.arr));
for(int i=0; i<maxn; i++)
ans.arr[i][i] = 1;
while(N){
if(N&1)
ans = ans*a;
a = a*a;
N /= 2;;
}
return ans;
}
int main(){
ll k,n,tmp[11];
matrix a;
scanf("%lld%lld",&k,&n);
memset(a.arr,0,sizeof(a.arr));
for(int i=0;i<k;i++){
if(i!=k-1)
a.arr[i][i+1]=1;
else
for(int j=0;j<k;j++)
a.arr[i][j]=1;
}
for(int i=0;i<k;i++)
tmp[i]=pow(2,i);
a=quick_pow(a,n-k);
ll ans=0;
for(int i=0;i<k;i++){
//cout<<tmp[i]<<" ";
ans+=a.arr[k-1][i]*tmp[i];
ans%=mod;
}
printf("%lld\n",ans);
/*for(int i=0;i<k;i++){
for(int j=0;j<k;j++){
printf("%lld ",a.arr[i][j]);
}
cout<<endl;
}*/
return 0;
}