Matrix Power Series POJ - 3233 矩陣幂次之和。

矩陣幂次之和。

自己想着想着就想到了一個解法，但是還沒送出，因為POJ崩了，做了一個FIB的前n項和，也是用了這個方法，AC了，相信是可以得。

送出了，是AC的

​​http://poj.org/problem?id=3233​​

我的思路是：

首先原矩陣保留着，然後需要擴大一倍

需要求1--->1的路徑數 <= k的，ans = （路徑數 = k的） ＋（路徑數 < k）的

等于k的很容易求，就是e^k然後e[1][1]就是答案，那麼小于k的，我們需要虛拟一個節點保留着

後新增一個節點3，e[1][3] = 1,  e[3][3] = 1是用來求 < k的數目的。

怎麼求，比如

這樣求到的e[1][1] = 1表明長度是2的有一種情況，但是長度是1的遺漏了，就是1--1本來那條，通過新增一條虛拟邊e[1][3]

這樣就把1--1原來的那條邊保留了下來，

1-->3這條邊是專為1服務的，是e[1][1]，也就是結尾點是1的情況的總數。是以會有一條e[3][3]的多餘邊，需要減去1。

而求1-->2的總數的時候，是e[1][2]（長度是k的總數） + e[1][4]（長度 < k的總數）這裡就不會多出一條邊了，因為本來的e[1][4] = 0的

這個是真真正正的保留了1--2這條邊了。

具體自己畫畫吧，感覺描述不清楚了。

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int maxn = 60 + 3;
struct Matrix {
    LL a[maxn][maxn];
    int row;
    int col;
}base;
//應對稀疏矩陣，更快。
struct Matrix matrix_mul(struct Matrix a, struct Matrix b, int MOD) { //求解矩陣a*b%MOD
    struct Matrix c = {0};  //這個要多次用到，棧配置設定問題，maxn不能開太大，
    //LL的時候更加是，空間是maxn*maxn的，這樣時間用得很多，4和5相差300ms
    c.row = a.row; //行等于第一個矩陣的行
    c.col = b.col; //列等于第二個矩陣的列
    for (int i = 1; i <= a.row; ++i) {
        for (int k = 1; k <= a.col; ++k) {
            if (a.a[i][k]) { //應付稀疏矩陣，0就不用枚舉下面了
                for (int j = 1; j <= b.col; ++j) {
                    c.a[i][j] += a.a[i][k] * b.a[k][j];
                    c.a[i][j] = (c.a[i][j] + MOD) % MOD; //負數取模
                }
            }
        }
    }
    return c;
}
struct Matrix quick_matrix_pow(struct Matrix ans, struct Matrix base, int n, int MOD) {
//求解a*b^n%MOD
    while (n) {
        if (n & 1) {
            ans = matrix_mul(ans, base, MOD);//傳數組不能亂傳,不滿足交換律
        }
        n >>= 1;
        base = matrix_mul(base, base, MOD);
    }
    return ans;
}
int n, k, MOD;
void work() {
    base.row = base.col = 2 * n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> base.a[i][j];
            base.a[i][j] %= MOD;
        }
    }
    for (int i = 1; i <= n; ++i) {
        base.a[i][n + i] = 1;
    }
    for (int i = n + 1; i <= 2 * n; ++i) {
        base.a[i][i] = 1;
    }
//    for (int i = 1; i <= 2 * n; ++i) {
//        for (int j = 1; j <= 2 * n; ++j) {
//            printf("%d ", base.a[i][j]);
//        }
//        printf("\n");
//    }
    Matrix I = {0};
    I.row = I.col = 2 * n;
    for (int i = 1; i <= 2 * n; ++i) {
        I.a[i][i] = 1;
    }
//    printf("\n");
    I = quick_matrix_pow(I, base, k, MOD);
//    for (int i = 1; i <= 2 * n; ++i) {
//        for (int j = 1; j <= 2 * n; ++j) {
//            printf("%d ", I.a[i][j]);
//        }
//        printf("\n");
//    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int ans = 0;
            ans += I.a[i][j];
            ans += I.a[i][n + j];
            ans %= MOD;
            if (i == j) ans = (ans - 1 + MOD) % MOD;
            printf("%d ", ans);
        }
        printf("\n");
    }
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    while (cin >> n >> k >> MOD) work();
    return 0;
}      

View Code

做了這個題

​​http://acm.hdu.edu.cn/showproblem.php?pid=5171​​

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int maxn = 6;
struct Matrix {
    LL a[maxn][maxn];
    int row;
    int col;
}base;
//應對稀疏矩陣，更快。
struct Matrix matrix_mul(struct Matrix a, struct Matrix b, int MOD) { //求解矩陣a*b%MOD
    struct Matrix c = {0};  //這個要多次用到，棧配置設定問題，maxn不能開太大，
    //LL的時候更加是，空間是maxn*maxn的，這樣時間用得很多，4和5相差300ms
    c.row = a.row; //行等于第一個矩陣的行
    c.col = b.col; //列等于第二個矩陣的列
    for (int i = 1; i <= a.row; ++i) {
        for (int k = 1; k <= a.col; ++k) {
            if (a.a[i][k]) { //應付稀疏矩陣，0就不用枚舉下面了
                for (int j = 1; j <= b.col; ++j) {
                    c.a[i][j] += a.a[i][k] * b.a[k][j];
                    c.a[i][j] = (c.a[i][j] + MOD) % MOD; //負數取模
                }
            }
        }
    }
    return c;
}
struct Matrix quick_matrix_pow(struct Matrix ans, struct Matrix base, int n, int MOD) {
//求解a*b^n%MOD
    while (n) {
        if (n & 1) {
            ans = matrix_mul(ans, base, MOD);//傳數組不能亂傳,不滿足交換律
        }
        n >>= 1;
        base = matrix_mul(base, base, MOD);
    }
    return ans;
}
const int MOD = 10000007;
int n, k;
int a[100000 + 20];
void work() {
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a + 1, a + 1 + n);
    Matrix I = {0};
    I.row = I.col = 4;
    for (int i = 1; i <= 4; ++i) I.a[i][i] = 1;
    I = quick_matrix_pow(I, base, k, MOD);
    Matrix F = {0};
    F.row = 1, F.col = 2;
    F.a[1][1] = a[n], F.a[1][2] = a[n - 1];
    Matrix b = {0};
    b.row = b.col = 2;
    for (int i = 1; i <= 2; ++i) {
        for (int j = 1; j <= 2; ++j) {
            int ans = I.a[i][j];
            ans += I.a[i][2 + j];
            ans %= MOD;
            if (i == j) ans = (ans - 1 + MOD) % MOD;
            b.a[i][j] = ans;
        }
    }
//    for (int i = 1; i <= 2; ++i) {
//        for (int j = 1; j <= 2; ++j) {
//            printf("%d ", b.a[i][j]);
//        }
//        printf("\n");
//    }
    F = matrix_mul(F, b, MOD);
    int ans = F.a[1][1];
    for (int i = 1; i <= n; ++i) {
        ans = (ans + a[i]) % MOD;
    }
    cout << ans << endl;
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    base.col = base.row = 4;
    base.a[1][1] = 1, base.a[1][2] = 1;
    base.a[2][1] = 1, base.a[2][2] = 0;
    for (int i = 1; i <= 2; ++i) {
        base.a[i][2 + i] = 1;
    }
    for (int i = 3; i <= 4; ++i) base.a[i][i] = 1;
    while (cin >> n >> k) work();
    return 0;
}