程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 3233 Matrix Power Series(矩陣優化)

POJ 3233 Matrix Power Series(矩陣優化)

編輯:C++入門知識

POJ 3233 Matrix Power Series(矩陣優化)


題意:求S[k] = A + A^2 + ..... + A^k

利用矩陣快速冪可以很快的求出A矩陣的k次方, 但是該題是求和, 如果還按照原來的方法, 將要計算k次, 復雜度無法承受。

我們可以構造一個矩陣 (A 0)

(E E)

此時令S[k] = E + A + A^2 + ..... + A^(k-1)

那麼 ( A^k ) ( A 0)(A^(k-1)) (A 0 )^k (E)

= =

(S[k] ) (E E)(S[k-1] ) (E E ) (0)

那麼, 我們只要計算出S[k+1] = E + A + .... + A^k

然後將對角線元素-1就行了。

細節參見代碼:

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int mod = 10007;
const int maxn = 100;
int T,n,m,k;
typedef vector vec;
typedef vector mat;
mat mul(mat &a, mat &b) {
    mat c(a.size(), vec(a[0].size()));
    for(int i = 0; i < a.size(); i++) {
        for(int k = 0; k < b.size(); k++) {
            for(int j = 0; j < b[0].size(); j++) {
                c[i][j] = (c[i][j] + a[i][k]*b[k][j]) % m;
            }
        }
    }
    return c;
}
mat pow(mat a, ll n) {
    mat b(a.size(), vec(a[0].size()));
    for(int i = 0; i < a.size(); i++) {
        b[i][i] = 1;
    }
    while(n > 0) {
        if(n & 1) b = mul(b, a);
        a = mul(a, a);
        n >>= 1;
    }
    return b;
}
int main() {
    scanf("%d%d%d",&n,&k,&m);
    mat a(2*n, vec(2*n));
    for(int i=0;i 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved