Luogu

LOJ

分析

设 $f_n$ 表示第 $n$ 个人带来的礼物数，$s_n$ 表示 $f_n$ 的前缀和，显然有 $s_n=s_{n-1}+f_n=2s_{n-1}+n^k$。

我们只要求出 $s_{n-1}$ 即可求出 $f_n=s_{n-1}+n^k$。

考虑矩阵快速幂。这个 $n^k$ 不是很好转移，可以考虑二项式定理
$$
(n+1)^k=\sum_{i=0}^k{k\choose i}n^i
$$
所以可以构造一个 $(k+2)\times (k+2)$ 的矩阵
$$
\begin{bmatrix}s_n&n^k&n^{k-1}&\cdots&n^0\end{bmatrix}\times\begin{bmatrix}2&0&0&\cdots&0\\{k\choose 0}&{k\choose 0}&0&\cdots&0\\{k\choose 1}&{k\choose 1}&{k-1\choose 0}&\cdots&0\\\vdots&\vdots&\vdots&\ddots&\vdots\\{k\choose k}&{k\choose k}&{k-1\choose k-1}&\cdots&{0\choose 0}\end{bmatrix}=\begin{bmatrix}s_{n+1}&(n+1)^k&(n+1)^{k-1}&\cdots&(n+1)^0\end{bmatrix}
$$
可能需要特判 $n\leq 2$ 的情况。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10+10;
const int mod=1e9+7;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

ll n; int k,C[N][N];

struct Matrix {
    int s[N][N];
    Matrix() { memset(s,0,sizeof(s)); }
    int* operator [](int i) { return s[i]; }
} A,M;
Matrix operator *(Matrix a,Matrix b) {
    Matrix c;
    for (int i=0;i<=k+1;++i)
        for (int j=0;j<=k+1;++j)
            for (int l=0;l<=k+1;++l)
                c[i][j]=(c[i][j]+1ll*a[i][l]*b[l][j])%mod;
    return c;
}
Matrix qpow(Matrix a,ll b) {
    Matrix c;
    for (int i=0;i<=k+1;++i) c[i][i]=1;
    for (;b;b>>=1,a=a*a) if (b&1) c=c*a;
    return c;
}

int main() {
    n=read(),k=read();
    if (n==1) { puts("1"); return 0; }
    if (n==2) { printf("%d\n",(1+qpow(2,k))%mod); return 0; }
    for (int i=C[0][0]=1;i<=k;++i)
        for (int j=C[i][0]=1;j<=k;++j)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    M[0][0]=2;
    for (int i=1;i<=k+1;++i) M[i][0]=C[k][i-1];
    for (int i=1;i<=k+1;++i)
        for (int j=i;j<=k+1;++j)
            M[j][i]=C[k-i+1][j-i];
    for (int i=0;i<=k+1;++i) A[0][i]=1;
    A=A*qpow(M,n-2);
    printf("%d\n",(A[0][0]+qpow(n%mod,k))%mod);
    return 0;
}