2020-2021:teams:no_morning_training:weekly:week9
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:weekly:week9 [2020/07/31 14:47] nomansland [王瑞琦] |
2020-2021:teams:no_morning_training:weekly:week9 [2020/07/31 16:15] (当前版本) 发源于 |
||
|---|---|---|---|
| 行 10: | 行 10: | ||
| 无 | 无 | ||
| ===== 冯宇扬 ===== | ===== 冯宇扬 ===== | ||
| + | ===比赛=== | ||
| + | cf 659 div 2\\ | ||
| + | [[2020-2021:teams:no_morning_training:fayuanyu:cf_r660d2|cf 660 div 2]] | ||
| ===== 常程 ===== | ===== 常程 ===== | ||
| ===比赛=== | ===比赛=== | ||
| 行 19: | 行 22: | ||
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
| ==== 王瑞琦 ==== | ==== 王瑞琦 ==== | ||
| + | 写了一道矩阵快速幂的模板题。 | ||
| + | ===来源=== | ||
| + | 洛谷P3390：[[https://www.luogu.com.cn/problem/P3390|【模板】矩阵快速幂]] | ||
| + | ===标签=== | ||
| + | 数学，矩阵乘法 | ||
| + | ===题意=== | ||
| + | 给出一个n*n的矩阵，计算其的k次方 | ||
| + | ===题解=== | ||
| + | 对矩阵运用快速幂=。=\\ | ||
| + | 快速幂：\\ | ||
| + | 对于n的k次方，可以不需要计算k次，只需计算出n^(k/2)，然后再开方即可（对于k为奇的情况要再乘一个n）\\ | ||
| + | 可以将复杂度降到O(logn)\\ | ||
| + | <hidden 代码> | ||
| + | <code c> | ||
| + | #include <stdio.h> | ||
| + | #define p 1000000007 | ||
| + | struct matrix{ | ||
| + | long long m[101][101]; | ||
| + | }; | ||
| + | typedef struct matrix Matrix; | ||
| + | long long n; | ||
| + | |||
| + | Matrix work(Matrix a,Matrix b) | ||
| + | { | ||
| + | Matrix tmp; | ||
| + | for (long long i=1;i<=n;i++) | ||
| + | for (long long j=1;j<=n;j++) | ||
| + | { | ||
| + | tmp.m[i][j]=0; | ||
| + | for (long long k=1;k<=n;k++) | ||
| + | tmp.m[i][j]=(tmp.m[i][j]+a.m[i][k]*b.m[k][j])%p; | ||
| + | } | ||
| + | return tmp; | ||
| + | } | ||
| + | |||
| + | Matrix ksm(Matrix a,long long m) | ||
| + | { | ||
| + | Matrix tmp=a,b=a; | ||
| + | m--; | ||
| + | while (m>0) | ||
| + | { | ||
| + | if (m%2==1) tmp=work(b,tmp); | ||
| + | b=work(b,b); | ||
| + | m=m/2; | ||
| + | } | ||
| + | return tmp; | ||
| + | } | ||
| + | |||
| + | int main() | ||
| + | { | ||
| + | long long k; | ||
| + | Matrix a; | ||
| + | scanf("%lld%lld",&n,&k); | ||
| + | for (long long i=1;i<=n;i++) | ||
| + | for (long long j=1;j<=n;j++) scanf("%lld",&a.m[i][j]); | ||
| + | a=ksm(a,k); | ||
| + | for (long long i=1;i<=n;i++) | ||
| + | { | ||
| + | for (long long j=1;j<=n;j++) | ||
| + | printf("%lld ",a.m[i][j]); | ||
| + | printf("\n"); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | ===comment=== | ||
| + | 一道模板题。矩阵快速幂的运用范围还是挺广的。 | ||
| + | |||
| ==== 冯宇扬 ==== | ==== 冯宇扬 ==== | ||
| + | 就[[2020-2021:teams:no_morning_training:fayuanyu:cf_r660d2|cf 660 div 2]]吧 | ||
| ==== 常程 ==== | ==== 常程 ==== | ||
| 本周摸了 | 本周摸了 | ||
2020-2021/teams/no_morning_training/weekly/week9.1596178061.txt.gz · 最后更改: 2020/07/31 14:47 由 nomansland
