首页 > 代码库 > HDU 1575 && 1757 矩阵快速幂&&构造矩阵入门

HDU 1575 && 1757 矩阵快速幂&&构造矩阵入门

2024-07-22 18:46:54   228人阅读

HDU 1575

Tr A

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2912    Accepted Submission(s): 2167


Problem Description
A为一个方阵，则Tr A表示A的迹（就是主对角线上各项的和），现要求Tr(A^k)%9973。
 

 

Input
数据的第一行是一个T，表示有T组数据。
每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据。接下来有n行，每行有n个数据，每个数据的范围是[0,9]，表示方阵A的内容。
 

 

Output
对应每组数据，输出Tr(A^k)%9973。
 

 

Sample Input
2
2 2
1 0
0 1
3 99999999
1 2 3
4 5 6
7 8 9
 

 

Sample Output
2
2686
 
 
 
 一个矩阵快速幂搞定。。
 
 1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8 #define MOD 9973 9 typedef __int64 LL;10 11 struct node{12     LL g[11][11];13 };14 15 int n, m;16 17 node cheng(node a,node b){18     node c;19     int i, j, k;20 21     memset(c.g,0,sizeof(c.g));22     for(i=0;i<n;i++){23         for(k=0;k<n;k++){24             if(!a.g[i][k]) continue;25             for(j=0;j<n;j++)26             c.g[i][j]=(c.g[i][j]+a.g[i][k]*b.g[k][j])%MOD;27         }28     }29     30     return c;31 }32 33 node pow(node a,int mm){34     node ans;35     int i, j;36     memset(ans.g,0,sizeof(ans.g));37     for(i=0;i<n;i++) ans.g[i][i]=1;38     while(mm){39         if(mm&1) ans=cheng(ans,a);40         a=cheng(a,a);41 mm>>=1;42     //    cout<<mm<<endl;43     }44     45     return ans;46 }47 48 main()49 {50     int t, i, j, k;51     cin>>t;52     while(t--){53         node a;54         scanf("%d %d",&n,&m);55         for(i=0;i<n;i++){56             for(j=0;j<n;j++)57             scanf("%I64d",&a.g[i][j]);58         }59         60         a=pow(a,m);61         62         LL ans=0;63         for(i=0;i<n;i++){64             ans=(ans+a.g[i][i])%MOD;65         }66         printf("%I64d\n",ans);67     }68 }
 
 
HDU 1757
A Simple Math Problem
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2751    Accepted Submission(s): 1628


Problem Description
Lele now is thinking about a simple function f(x).

If x < 10 f(x) = x.
If x >= 10 f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10);
And ai(0<=i<=9) can only be 0 or 1 .

Now, I will give a0 ~ a9 and two positive integers k and m ,and could you help Lele to caculate f(k)%m.
 
 
Input
The problem contains mutiple test cases.Please process to the end of file.
In each case, there will be two lines.
In the first line , there are two positive integers k and m. ( k<2*10^9 , m < 10^5 )
In the second line , there are ten integers represent a0 ~ a9.
 
 
Output
For each case, output f(k) % m in one line.
 
 
Sample Input
10 9999
1 1 1 1 1 1 1 1 1 1
20 500 
1 0 1 0 1 0 1 0 1 0
 
 
Sample Output
45 
104
 
 
题目意思：
给出f[x]怎么得到，然后求f[k]%m。
 
思路：
这道题可以找通项公式来算，但是比较麻烦，而这道题很明显可以用矩阵相乘来算。
已知  当x<10  ,f[x]=x；
所以咱们可以由以下矩阵相乘算以后的项 ，如下：
|                |   |f[0]|    |f[1]|
|                |   |f[1]|    |f[2]|
|                |   |f[2]|    |f[3]|
|                |   |f[3]|    |f[4]|
|                | * |f[4]| =  |f[5]|
|                |   |f[5]|    |f[6]|
|                |   |f[6]|    |f[7]|
|                |   |f[7]|    |f[8]|
|                |   |f[8]|    |f[9]|
|                |   |f[9]|    |f[10]|
   （构造的矩阵a）     （矩阵b）  （矩阵c）
当x<10的时候直接输出即可，当x>10  ,a^(x-9)*b就可以得到f[x]了。
而a^(x-9)用矩阵快速幂可以快速算出，时间复杂度为O(logn)。
很容易得出构造的矩阵a为：
0,1,0,0,0,0,0,0,0,0
0,0,1,0,0,0,0,0,0,0
0,0,0,1,0,0,0,0,0,0
0,0,0,0,1,0,0,0,0,0
0,0,0,0,0,1,0,0,0,0
0,0,0,0,0,0,1,0,0,0
0,0,0,0,0,0,0,1,0,0
0,0,0,0,0,0,0,0,1,0
0,0,0,0,0,0,0,0,0,1
a9,a8,a7,a6,a5,a4,a3,a2,a1,a0
 
代码如下：
 
 
 1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #include <vector> 6 #include <queue> 7 using namespace std; 8  9 typedef __int64 LL;10 int n;11 LL MOD;12 13 struct node{14     LL g[10][10];15 };16 int a[10];17 18 node init(){19     node c;20     int i;21     memset(c.g,0,sizeof(c.g));22     for(i=0;i<9;i++) c.g[i][i+1]=1;23     for(i=0;i<10;i++) c.g[9][i]=a[9-i];24     25     26     return c;27 }28 29 node cheng(node A,node B){30     node C;31     memset(C.g,0,sizeof(C.g));32     int i, j, k;33     for(i=0;i<10;i++){              //这里有个小技巧，把原本俩矩阵相乘的代码中j和k的位置换一下 ，很明显的提高了时间效率 34         for(k=0;k<10;k++){35             if(!A.g[i][k]) continue;36             for(j=0;j<10;j++)37             C.g[i][j]=(C.g[i][j]+A.g[i][k]*B.g[k][j])%MOD;38         }39     }40     return C;41 }42 43 node pow(node c,int mm){44     node A;45     int i;46     memset(A.g,0,sizeof(A.g));47     for(i=0;i<10;i++) A.g[i][i]=1;48     while(mm){49         if(mm&1) A=cheng(A,c);50         c=cheng(c,c);51         mm>>=1;52     }53     return A;54 }55 56 main()57 {58     int i, j, k;59     __int64 f[]={0,1,2,3,4,5,6,7,8,9};60 61     while(scanf("%d %I64d",&n,&MOD)==2){62         for(i=0;i<10;i++) scanf("%d",&a[i]);63         if(n<10) {printf("%I64d\n",f[n]);continue;}64         node c=init();  //构造矩阵 65             66         67         n=n-9;68         c=pow(c,n);    //矩阵快速幂优化矩阵相乘 69         LL ans=0;70         for(i=0;i<10;i++)71         ans=(ans+c.g[9][i]*f[i])%MOD;72         printf("%I64d\n",ans);73         74     }75 }
 
 
 
HDU 1575 && 1757   矩阵快速幂&&构造矩阵入门






























        

            
                
                  
                
                

                    联系

                    我们