## 【CodeForces-392C】Yet Another Number Sequence

【CodeForces-392C】Yet Another Number Sequence

Solution:

#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;
}