自然数幂和

题目描述

给定 𝑛 和 𝑘，计算 $\Sigma^{n}_{i=1}i^k$ 对 $10^9+7$ 取模的结果。

输入格式

第一行一个数 $T(1\le T\le 100)$，表示数据组数。
接下来 $T$ 行，每行两个整数 $n,k(1\le n\le 10^9,1\le k\le 10)$。

输出格式

输出 $T$ 行，表示每组数据的答案。

测试用例

输入

6
1 10
2 2
2 3
3 2
3 3
1000000000 9

输出

1
5
9
14
36
12313161

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

const ll N = 12;//方阵的大小
ll mod = 1e9 + 7;//模
struct Matrix {
    ll x[N][N];
    Matrix() {
        memset(x, 0, sizeof(x));
    }
    Matrix(const Matrix &b) {
        memcpy(x, b.x, sizeof(x));
    }
    Matrix operator*(const Matrix &b) const {
        Matrix c;
        for (ll i = 0; i < N; i++)
            for (ll j = 0; j < N; j++) {
                c.x[i][j] = 0;
                for (ll k = 0; k < N; k++) {
                    c.x[i][j] += x[i][k] * b.x[k][j] % mod;
                    c.x[i][j] %= mod;
                }
            }
        return c;
    }
};
//矩阵快速幂
Matrix fastpow(Matrix a, ll n) {
    Matrix res;
    for (ll i = 0; i < N; i++)
        res.x[i][i] = 1;
    while (n) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}

//求n的阶乘
ll jc(ll n) {
    ll ans = 1;
    for (ll i = 1; i <= n; ++i) {
        ans = ans * i;
    }
    return ans;
}

//组合数c(n,m) n>=m
ll c(ll n, ll m) {
    return jc(n) / (jc(m) * jc(n - m));
}

int main() {
    ll t, n, k, w;//w为方阵的宽度
    cin >> t;
    for (ll i = 1; i <= t; ++i) {
        cin >> n >> k;
        w = k + 2;//转移矩阵的宽度
        Matrix a;
        a.x[0][0] = 1;//初始化转移矩阵第一行
        for (ll i = 1; i < w; i++) {
            a.x[0][i] = c(k, i - 1);
        }
        for (ll i = 1; i < w; i++) {//初始化转移矩阵剩下的行
            for (ll j = 0; j < w; j++) {
                if (j >= i) {
                    a.x[i][j] = c(k + 1 - i, j - i);
                }
            }
        }
        a = fastpow(a, n - 1);
        ll ans = 0;
        for (ll i = 0; i < w; i++) {
            ans = (a.x[0][i] % mod + ans % mod) % mod;
        }
        cout << ans << "\n";
    }
    return 0;
}