模板:
- #include
- using namespace std;
- const int N=1010,mod=1e9+7;
- long long a[N][N],ans[N][N],temp[N][N],n,k;
- void calculate()
- {
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- {
- temp[i][j]=ans[i][j];
- ans[i][j]=0;
- }
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- for(int k=1;k<=n;k++)
- ans[i][j]=(ans[i][j]+(a[i][k]*temp[k][j])%mod)%mod;
- }
- void change()
- {
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- {
- temp[i][j]=a[i][j];
- a[i][j]=0;
- }
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- for(int k=1;k<=n;k++)
- a[i][j]=(a[i][j]+(temp[i][k]*temp[k][j])%mod)%mod;
- }
- void quickpow(long long x)
- {
- while(x)
- {
- if(x%2) calculate();
- x/=2;
- change();
- }
- }
- int main()
- {
- scanf("%lld%lld",&n,&k);
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- {
- scanf("%lld",&a[i][j]);
- ans[i][j]=a[i][j];
- }
- quickpow(k-1);
- for(int i=1;i<=n;i++)
- {
- for(int j=1;j<=n;j++)
- printf("%lld ",ans[i][j]);
- printf("\n");
- }
- return 0;
- }
但是真正我们使用矩阵乘法通常是在数列上,比如斐波那契
这里我们想把一个 1*2 的矩阵{ f [ i ] , f [ i - 1] } 转换成 { f [ i ] +f [ i - 1] , f [ i ]}
那么我们就要乘上(第一行)1 1 (第二行) 1 0 的矩阵。同样的,如果是广义斐波那契,我们只需要更改第一行为:a,b 就可以解决线性数列。
- #include
- using namespace std;
- #define int long long
- const int mod=1e9+7;
- struct node{int s[3][3];}ans,base;
- int n;
- node mul(node a,node b)
- {
- node res;
- for(int i=1;i<=2;i++)
- for(int j=1;j<=2;j++)
- {
- int sum=0;
- for(int k=1;k<=2;k++)
- sum=(sum+a.s[i][k]*b.s[k][j])%mod;
- res.s[i][j]=sum;
- }
- return res;
- }
- void qp(int x)
- {
- ans.s[1][1]=ans.s[1][2]=1;
- base.s[1][1]=base.s[1][2]=base.s[2][1]=1;
- while(x)
- {
- if(x&1) ans=mul(ans,base);
- base=mul(base,base);
- x>>=1;
- }
- }
- signed main()
- {
- scanf("%lld",&n);
- if(n<=2) printf("1");
- else
- {
- qp(n-2);
- printf("%lld",ans.s[1][1]);
- }
- return 0;
- }
从题面来看非常像过河卒,可以想到要找状态转移方程。一个位置可能是从三行转移过来
我们把每次状态转移设计到的 列在一个1*6的矩阵里:
- #include
- using namespace std;
- #define int long long
- const int mod=30011;
- int n,m,a[1010][1010],b[1010][1010];
- int p[1010][1010],k[1010][1010];
- void node(int A[][1010],int B[][1010])
- {
- memset(a,0,sizeof a);
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- for(int k=1;k<=n;k++)
- a[i][j]=(a[i][j]+A[i][k]*B[k][j])%mod;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- A[i][j]=a[i][j];
- }
- void qp(int A[][1010],int x)
- {
- memset(a,0,sizeof a);
- x--;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- b[i][j]=k[i][j];
- while(x)
- {
- if(x&1) node(b,A);
- node(A,A);
- x>>=1;
- }
- }
- signed main()
- {
- scanf("%lld%lld",&n,&m);
- //Specialjudge
- if(m==2)
- {
- if(n==1||n==2) puts("1");
- else puts("0");
- return 0;
- }
- if(m==3)
- {
- if(n==1||n==3) puts("1");
- else if(n==2) puts("2");
- else puts("3");
- return 0;
- }
- for(int i=1;i<=n;i++) k[i][i]=k[i+n][i]=k[i][i+n]=1;
- for(int i=1;i
1][i]=k[i][i+1]=1; - n*=2;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=n;j++)
- p[i][j]=k[i][j];
- qp(k,m-2);
- node(p,b);
- printf("%lld",(p[1][n/2]-b[1][n]+mod)%mod);
- return 0;
- }
活动地址:CSDN21天学习挑战赛https://marketing.csdn.net/p/bdabfb52c5d56532133df2adc1a728fd