• 矩阵快速幂+矩阵乘法构造


    模板:

    1. #include
    2. using namespace std;
    3. const int N=1010,mod=1e9+7;
    4. long long a[N][N],ans[N][N],temp[N][N],n,k;
    5. void calculate()
    6. {
    7. for(int i=1;i<=n;i++)
    8. for(int j=1;j<=n;j++)
    9. {
    10. temp[i][j]=ans[i][j];
    11. ans[i][j]=0;
    12. }
    13. for(int i=1;i<=n;i++)
    14. for(int j=1;j<=n;j++)
    15. for(int k=1;k<=n;k++)
    16. ans[i][j]=(ans[i][j]+(a[i][k]*temp[k][j])%mod)%mod;
    17. }
    18. void change()
    19. {
    20. for(int i=1;i<=n;i++)
    21. for(int j=1;j<=n;j++)
    22. {
    23. temp[i][j]=a[i][j];
    24. a[i][j]=0;
    25. }
    26. for(int i=1;i<=n;i++)
    27. for(int j=1;j<=n;j++)
    28. for(int k=1;k<=n;k++)
    29. a[i][j]=(a[i][j]+(temp[i][k]*temp[k][j])%mod)%mod;
    30. }
    31. void quickpow(long long x)
    32. {
    33. while(x)
    34. {
    35. if(x%2) calculate();
    36. x/=2;
    37. change();
    38. }
    39. }
    40. int main()
    41. {
    42. scanf("%lld%lld",&n,&k);
    43. for(int i=1;i<=n;i++)
    44. for(int j=1;j<=n;j++)
    45. {
    46. scanf("%lld",&a[i][j]);
    47. ans[i][j]=a[i][j];
    48. }
    49. quickpow(k-1);
    50. for(int i=1;i<=n;i++)
    51. {
    52. for(int j=1;j<=n;j++)
    53. printf("%lld ",ans[i][j]);
    54. printf("\n");
    55. }
    56. return 0;
    57. }

    但是真正我们使用矩阵乘法通常是在数列上,比如斐波那契

    斐波那契数列 

    这里我们想把一个 1*2 的矩阵{ f [ i ] , f [ i - 1] } 转换成 { f [ i ] +f [ i - 1] , f [ i ]}

    那么我们就要乘上(第一行)1 1 (第二行) 1 0 的矩阵。同样的,如果是广义斐波那契f[i]=a*f[i-1]+b*f[i-2],我们只需要更改第一行为:a,b 就可以解决线性数列。

    1. #include
    2. using namespace std;
    3. #define int long long
    4. const int mod=1e9+7;
    5. struct node{int s[3][3];}ans,base;
    6. int n;
    7. node mul(node a,node b)
    8. {
    9. node res;
    10. for(int i=1;i<=2;i++)
    11. for(int j=1;j<=2;j++)
    12. {
    13. int sum=0;
    14. for(int k=1;k<=2;k++)
    15. sum=(sum+a.s[i][k]*b.s[k][j])%mod;
    16. res.s[i][j]=sum;
    17. }
    18. return res;
    19. }
    20. void qp(int x)
    21. {
    22. ans.s[1][1]=ans.s[1][2]=1;
    23. base.s[1][1]=base.s[1][2]=base.s[2][1]=1;
    24. while(x)
    25. {
    26. if(x&1) ans=mul(ans,base);
    27. base=mul(base,base);
    28. x>>=1;
    29. }
    30. }
    31. signed main()
    32. {
    33. scanf("%lld",&n);
    34. if(n<=2) printf("1");
    35. else
    36. {
    37. qp(n-2);
    38. printf("%lld",ans.s[1][1]);
    39. }
    40. return 0;
    41. }

    [SHOI2013]超级跳马 

    从题面来看非常像过河卒,可以想到要找状态转移方程。一个位置可能是从三行转移过来

    我们把每次状态转移设计到的f[i][j] 列在一个1*6的矩阵里:

     

    1. #include
    2. using namespace std;
    3. #define int long long
    4. const int mod=30011;
    5. int n,m,a[1010][1010],b[1010][1010];
    6. int p[1010][1010],k[1010][1010];
    7. void node(int A[][1010],int B[][1010])
    8. {
    9. memset(a,0,sizeof a);
    10. for(int i=1;i<=n;i++)
    11. for(int j=1;j<=n;j++)
    12. for(int k=1;k<=n;k++)
    13. a[i][j]=(a[i][j]+A[i][k]*B[k][j])%mod;
    14. for(int i=1;i<=n;i++)
    15. for(int j=1;j<=n;j++)
    16. A[i][j]=a[i][j];
    17. }
    18. void qp(int A[][1010],int x)
    19. {
    20. memset(a,0,sizeof a);
    21. x--;
    22. for(int i=1;i<=n;i++)
    23. for(int j=1;j<=n;j++)
    24. b[i][j]=k[i][j];
    25. while(x)
    26. {
    27. if(x&1) node(b,A);
    28. node(A,A);
    29. x>>=1;
    30. }
    31. }
    32. signed main()
    33. {
    34. scanf("%lld%lld",&n,&m);
    35. //Specialjudge
    36. if(m==2)
    37. {
    38. if(n==1||n==2) puts("1");
    39. else puts("0");
    40. return 0;
    41. }
    42. if(m==3)
    43. {
    44. if(n==1||n==3) puts("1");
    45. else if(n==2) puts("2");
    46. else puts("3");
    47. return 0;
    48. }
    49. for(int i=1;i<=n;i++) k[i][i]=k[i+n][i]=k[i][i+n]=1;
    50. for(int i=1;i1][i]=k[i][i+1]=1;
    51. n*=2;
    52. for(int i=1;i<=n;i++)
    53. for(int j=1;j<=n;j++)
    54. p[i][j]=k[i][j];
    55. qp(k,m-2);
    56. node(p,b);
    57. printf("%lld",(p[1][n/2]-b[1][n]+mod)%mod);
    58. return 0;
    59. }

    活动地址:CSDN21天学习挑战赛https://marketing.csdn.net/p/bdabfb52c5d56532133df2adc1a728fd

  • 相关阅读:
    重写DATAGRID控件,当对行编辑后重LOAD后可定位到最后点击的那一行。
    NC56 自定义查询的维护
    使用QEMU+GDB调试操作系统代码
    【SpringBoot】SpringBoot2之编写第一个HelloWorld
    某游戏公司Java面试八股文总结
    android_logcat_4.4
    Ubuntu-24.04-live-server-amd64安装界面中文版
    C++中为什么要创建堆区域数据
    用Python实现链式调用
    java-php-net-python-图书馆选择计算机毕业设计程序
  • 原文地址:https://blog.csdn.net/m0_60137414/article/details/126023241