poj 3070 矩阵快速幂

￡神魔★判官ぃ 2022-08-07 14:53 255阅读 0赞 
  1. poj3070
  2. #include <cstdio>
  3. #include <cstring>
  4. using namespace std;
  6. #define M_H 2
  7. #define M_L 2
  9. typedef struct ma
  10. {
  11.     int h, l;
  12.     int a[M_H][M_L];
  13. }ma;
  14. ma need, anser;
  15. void init()
  16. {
  17.     need.h=2;   need.l=2;
  18.     anser.h=2;  anser.l=2;
  19.     need.a[0][0]=1; anser.a[0][0]=1;
  20.     need.a[0][1]=1; anser.a[0][1]=0;
  21.     need.a[1][0]=1; anser.a[1][0]=0;
  22.     need.a[1][1]=0; anser.a[1][1]=1;
  23. }
  25. ma multi(ma a, ma b)
  26. {
  27.     ma c;
  29.     c.h=a.h;  c.l=b.l;
  30.     for(int i=0; i<c.h; i++) for(int j=0; j<c.l; j++) c.a[i][j]=0;
  32.     for(int i=0; i<c.h; i++){
  33.         for(int j=0; j<c.l; j++){
  34.             int ans=0;
  35.             for(int k=0; k<a.h; k++){
  36.                 ans += (a.a[i][k] * b.a[k][j])%10000;
  37.             }
  38.             c.a[i][j]=ans%10000;
  39.         }
  40.     }
  41.     return c;
  42. }
  43. int main()
  44. {
  45.     int m;
  47.     while( scanf("%d", &m) != -1 ){
  48.         if(m==-1) break;
  49.         init();
  50.         while(m>0){
  51.             if(m&1){
  52.                 anser = multi(anser, need);
  53.             }
  54.             need = multi(need, need);
  55.             m = m>>1;
  56.         }
  57.         printf("%d\n", anser.a[0][1]%10000);
  58.     }
  60.     return 0;
  61. }

发表评论

表情：
评论列表 （有 0 条评论，255人围观）

还没有评论，来说两句吧...

相关阅读