[HDU 1757] A Simple Math Problem （矩阵快速幂） - c语言编程

TOP

[HDU 1757] A Simple Math Problem （矩阵快速幂）

2015-01-22 21:21:11 来源: 作者: 【大中小】浏览:44次

题目大意：

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 .
现在给你k和m，求f(k) % m。

解题思路：

f(x) = a0 * f(x-1) + a1 * f(x-2) + a2 * f(x-3) + …… + a9 * f(x-10)

其中k为10^9数量级，必然不能用递推的方式做。这类题目可以通过构造矩阵，用矩阵快速幂来做。

构造的矩阵是:

|0 1 0 ......... 0| |f0| |f1 |
|0 0 1 0 ....... 0| |f1| |f2 |
|................1| * |..| = |...|
|a9 a8 .........a0| |f9| |f10|

代码：

/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #define INF (1<<30) #define PI acos(-1.0) #define mem(a, b) memset(a, b, sizeof(a)) #define For(i, n) for (int i = 0; i < n; i++) typedef long long ll; using namespace std; const int maxn = 20; const int maxm = 20; ll mod, k; struct Matrix { int n, m; int a[maxn][maxm]; void clear() { n = m = 0; memset(a, 0, sizeof(a)); } Matrix operator * (const Matrix &b) const { //实现矩阵乘法 Matrix tmp; tmp.clear(); tmp.n = n; tmp.m = b.m; for (int i = 0; i < n; i++) for (int j = 0; j < b.m; j++) for (int k = 0; k < m; k++) { tmp.a[i][j] += a[i][k] * b.a[k][j]; tmp.a[i][j] %= mod; } return tmp; } }; Matrix A, B; void init() { A.clear(); //矩阵A是构造的矩阵 A.n = A.m = 10; for (int i = 0; i < 9; i++) A.a[i][i + 1] = 1; B.clear(); B.n = 10; B.m = 1; //矩阵B是f(x)的前10个数 for (int i = 0; i < 10; i++) B.a[i][0] = i; } Matrix Matrix_pow(Matrix A, ll k, ll mod) { //矩阵快速幂 Matrix res; res.clear(); res.n = res.m = 10; for (int i = 0; i < 10; i++) res.a[i][i] = 1; while(k) { if (k & 1) res = A * res; k >>= 1; A = A * A; } return res; } int main () { init(); while(cin>>k>>mod) { int x; for (int i = 0; i < 10; i++) { scanf("%d", &x); A.a[9][9 - i] = x; } if (k < 10) { printf("%lld\n", k % mod); } else { Matrix res = Matrix_pow(A, k - 9, mod); res = res * B; cout<


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：C和指针（pointers on C）――第..	下一篇：hdu3592 World Exhibition --- 差..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: