就..挺普通的一道题..自己学一下怎么推式子就可以...细节不多但是我还是日常爆细节..比如说循环写成从负数开始...
只求ac不求美观的丑陋的代码....
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 const int maxn=110; 9 const double eps=1e-8; 10 const long long modn=7777777; 11 int n,m; 12 long long f[11]={}; 13 struct mat{ 14 long long e[11][11]; 15 }; 16 mat pro(mat x,mat y){ 17 mat z; 18 for(int i=1;i<=n;i++){ 19 for(int j=1;j<=n;j++){ 20 z.e[i][j]=0; 21 for(int w=1;w<=n;w++){ 22 z.e[i][j]+=x.e[i][w]*y.e[w][j]; 23 z.e[i][j]%=modn; 24 } 25 } 26 } 27 return z; 28 } 29 mat pow(mat x,int k){ 30 mat z; 31 bool f=1; 32 while(k){ 33 if(k%2==1){ 34 if(f){ 35 z=x;f=0; 36 } 37 else{ 38 z=pro(x,z); 39 } 40 } 41 k/=2; 42 x=pro(x,x); 43 } 44 return z; 45 } 46 int main(){ 47 while(~scanf("%d%d",&n,&m)){ 48 f[0]=1; 49 for(int i=1;i<=n;i++){ 50 f[i]=0; 51 for(int j=0;j<i;j++){ 52 f[i]+=f[j]; 53 } 54 f[i]%=modn; 55 } 56 if(m>n){ 57 mat a; 58 for(int i=1;i<=n;i++){ 59 for(int j=1;j<=n;j++){ 60 a.e[i][j]=0; 61 } 62 } 63 for(int i=1;i<n;i++){ 64 a.e[i][i+1]=1; 65 a.e[n][i]=1; 66 }a.e[n][n]=1; 67 a=pow(a,m-n+1); 68 long long ans=0; 69 for(int i=1;i<=n;i++){ 70 ans+=a.e[n][i]*f[i-1]; 71 ans%=modn; 72 } 73 printf("%lld ",ans); 74 } 75 else{ 76 cout<<f[m]<<endl; 77 } 78 } 79 return 0; 80 }