tzoj7929: Matrix Power Series

题意

给定一个n*n大小的矩阵A，求以A为公比的等比数列的前k项和。

解题思路

直接从1到k矩阵快速幂每项相加肯定是会超时的，而如果用公式计算需要求逆矩阵非常麻烦，而且有可能会溢出。

因此我们使用分治求解。

当n为奇数时，

 当n为偶数时，

 分治求解即可。

#include <bits/stdc++.h>
using namespace std;

struct matrix
{
    int a[31][31];
};

int n, k, m;
matrix st, base;
matrix add(matrix a, matrix b)
{
    matrix res;
    for (int i = 1; i <= n;i++)
        for (int j = 1; j <= n;j++)
            res.a[i][j] = (a.a[i][j] + b.a[i][j]) % m;
    return res;
}
matrix multi(matrix a, matrix b)
{
    matrix res;
    memset(res.a, 0, sizeof(res.a));
    for (int i = 1;i<=n;i++)
        for (int j = 1; j <= n;j++)
            for (int p = 1; p <= n;p++)
                res.a[i][j] = (res.a[i][j] + a.a[i][p] * b.a[p][j]) % m;
    return res;
}
matrix fastpow(int p)
{
    matrix a = st;
    matrix b = base;
    while(p)
    {
        if(p&1)
            b = multi(b, a);
        a = multi(a, a);
        p = p >> 1;
    }
    return b;
}
matrix dfs(int p)
{
    if(p==1)
        return st;
    matrix ans, temp;
    ans = dfs(p / 2);
    temp = fastpow(p / 2);
    ans = add(ans, multi(ans, temp));
    if(p&1)
        ans = add(ans, fastpow(p));
    return ans;
}
signed main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k >> m;
    for (int i = 1; i <= n;i++)
        for (int j = 1; j <= n;j++)
        {
            cin >> st.a[i][j];
            if(i==j)
                base.a[i][j] = 1;
            else
                base.a[i][j] = 0;
        }
    matrix res;
    res = dfs(k);
    for (int i = 1;i<=n;i++)
    {
        for (int j = 1; j <= n;j++)
        {
            if(j!=1)
                cout<<" ";
            cout << res.a[i][j];
        }
        cout << endl;
    }
        return 0;
}