【CodeForces-392C】Yet Another Number Sequence

【CodeForces-392C】Yet Another Number Sequence

问题链接:https://vjudge.net/problem/CodeForces-392C

Solution:

我们将每一个\(A_i\)展开,发现它是许多项的和,准确来说,是以前出现过的项乘上一个组合数,根据这个建立转移矩阵。

参考了:https://www.cnblogs.com/MyWither/p/3556523.html,感谢博主分享。

#include <iostream>
using namespace std;

typedef long long LL;
const int LIM = 90;
const int SIZE = 50;
const LL MOD = 1e9 + 7;
LL n, C[SIZE][SIZE];
int k;

struct Matrix {
    LL v[LIM][LIM];
    int size;
    Matrix operator * (const Matrix &m) const {
        Matrix ret = {{0}};
        ret.size = size;
        for (int i = 0; i < size; i++)
            for (int k = 0; k < size; k++)
                if (v[i][k])
                    for (int j = 0; j < size; j++)
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j] % MOD) % MOD;
        return ret;
    }
};

Matrix fastPow(LL p, Matrix base) {
    Matrix ret = {{0}};
    ret.size = base.size;
    for (int i = 0; i < ret.size; i++) ret.v[i][i] = 1;
    while (p) {
        if (p & 1) ret = base * ret;
        p >>= 1;
        if (p) base = base * base;
    }
    return ret;
}

void buildC() {
    for (int i = 0; i <= k; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
    }
}

int main(void) {
    scanf("%lld%d", &n, &k);
    buildC();
    Matrix base = {{0}};
    base.size = (k + 1) * 2 + 1;
    for (int i = 0; i <= k; i++)
        for (int j = 0; j <= i; j++)
            base.v[i][j] = base.v[i][j + k + 1] = base.v[i + k + 1][j] = C[i][j];
    base.v[base.size - 1][base.size - 1] = base.v[base.size - 1][k] = 1;
    base = fastPow(n, base);
    LL ans = 0;
    for (int i = 0; i < base.size - 1; i++)
        ans = (ans + base.v[base.size - 1][i]) % MOD;
    printf("%lld\n", ans);
    return 0;
}