首页 > 代码库 > Hdu5015 233 Matrix矩阵

Hdu5015 233 Matrix矩阵

2024-07-30 07:39:37   222人阅读

每一列能由前一列推过来，构造一个(n+2)*(n+2)的矩阵B，第k列 就等于  所构造的第一列A*B^(k-1)

比如

233                            10    10    10    0           2333

a1+233            *                1      1      0    =     a1+233+2333

a1+a2+233                                1      0           a1+a2+233+a1+233+2333

3                                1      1     1      1           3

#include <cstdio>#include <algorithm>#include <iostream>#include <string.h>typedef long long LL;using namespace std;const LL mod = 10000007;LL n;struct Matrix{    LL m[15][15];};Matrix Mul(Matrix a, Matrix b){    Matrix ans;    for (LL i = 0; i < n + 2; i++){        for (LL j = 0; j < n + 2; j++){            ans.m[i][j] = 0;            for (LL k = 0; k < n + 2; k++){                ans.m[i][j] += a.m[i][k] * b.m[k][j];                ans.m[i][j] %= mod;            }        }    }    return ans;}Matrix quick(Matrix a, LL b){    Matrix ans;    for (LL i = 0; i < n + 2; i++)    for (LL j = 0; j < n + 2; j++)        ans.m[i][j] = (i == j);    while (b){        if (b & 1) ans = Mul(ans, a);        b >>= 1;        a = Mul(a, a);    }    return ans;}Matrix init(){    Matrix ans;    for (LL i = 0; i < n + 2; i++)    for (LL j = 0; j < n + 2; j++)        ans.m[i][j] = 0;    for (LL i = 0; i < n + 1; i++)        ans.m[0][i] = 10;    for (LL i = 1; i < n + 1; i++){        for (LL j = i; j < n + 1; j++)            ans.m[i][j] = 1;    }    for (LL i = 0; i < n + 2; i++)        ans.m[n + 1][i] = 1;    return ans;}int main(){    LL a[1000];    LL k;    while (cin >> n >> k){        for (LL i = 1; i < n + 1; i++)            cin >> a[i];        a[0] = 233; a[n + 1] = 3;        for (LL i = 1; i<n + 1; i++)            a[i] += a[i - 1];        Matrix gao = init();        gao = quick(gao, k - 1);        LL sum = 0;        for (LL i = 0; i < n + 2; i++){            sum += a[i] * gao.m[i][n];            sum %= mod;        }        cout << sum << endl;    }    return 0;}

 

Hdu5015 233 Matrix矩阵


联系
我们