「题解」「SNOI2017」礼物 gift

SNOI2017 D1T1 神仙题目。

（未完待续）

题目链接：Luogu P5364/LibreOJ 2253/SNOI2017 D1T1。

题目

题目描述

热情好客的小猴子请森林中的朋友们吃饭，他的朋友被编号为 $1\sim N$，每个到来的朋友都会带给他一些礼物：大香蕉。其中，第一个朋友会带给他 $1$ 个大香蕉，之后，每一个朋友到来以后，都会带给他之前所有人带来的礼物个数再加他的编号的 $K$ 次方那么多个。

现在，小猴子好奇自己到底能收到第 $N$ 个朋友多少礼物，因此拜托于你了，结果对 $10^9+7$ 取模。

数据范围

时空限制

题解

本题有多种做法，下面介绍一些正解。

事先约定：用 $a _ i$ 表示第 $i$ 个朋友的礼物个数。

解法 A（矩阵快速幂）

解法 A 利用了 矩阵快速幂 加速递推，时间复杂度为 $\Theta(k^3\log _ 2n)$。

思路

不妨设
$$s _ i=\sum^n _ {i=1}a _ i$$

那么我们有
$$\begin{aligned}s _ i&=s _ {i-1}+(s _ {i-1}+i^k)\\&=2s _ {i-1}+i^k\end{aligned}$$

考虑如何将 $i^k$ 表示为可递推的形式。

不难发现我们可以用二项式定理，那么我们有：
$$(i+1)^k=\sum^k _ {j=0}\binom{k}{j}i^j$$

继而
$$(i+1)^k=i^k+\binom{k}{1}i^{k-1}+\binom{k}{2}i^{k-2}+\cdots+\binom{k}{k}i^0$$

所以我们可以写出转移矩阵 $\text{T}$
$$
\begin{bmatrix}
2&0&0&\cdots&0\\
1&\binom{k}{k}&0&\cdots&0\\
0&\binom{k}{k-1}&\binom{k-1}{k-1}&\cdots&0\\
\cdots&\cdots&\cdots&\cdots&\cdots\\
0&\binom{k}{0}&\binom{k-1}{0}&\cdots&\binom{0}{0}
\end{bmatrix}
$$

同时，我们记录初始矩阵为 $\text{S}$
$$\begin{bmatrix}0,1,1,\cdots,1\end{bmatrix}$$

不难发现，答案就是 $\text{S}\times\text{T}^n-\text{S}\times\text{T}^{n-1}$ 的第一项，这种做法的时间复杂度为 $\Theta(k^3\log _ 2n)$。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define MOD 1000000007

const int MAXK=500+5;
const int MAXSIZE=500+5;

struct Matrix{
    int n,m;
    int unit[MAXK][MAXK];
    inline Matrix(reg int n,reg int m,reg int x=0):n(n),m(m){
        for(reg int i=0;i<n;++i)
            for(reg int j=0;j<m;++j)
                unit[i][j]=((i==j)?x:0);
        return;
    }
    inline Matrix operator*(const Matrix& a){
        Matrix res(n,a.m);
        reg int r;
        for(reg int i=0;i<n;++i)
            for(reg int k=0;k<m;++k){
                r=unit[i][k];
                for(reg int j=0;j<a.m;++j)
                    res.unit[i][j]=(res.unit[i][j]+1ll*r*a.unit[k][j]%MOD)%MOD;
            }
        return res;
    }
    inline Matrix operator^(reg ll exp){
        Matrix res(n,m,1),x=*this;
        while(exp){
            if(exp&1)
                res=res*x;
            x=x*x;
            exp>>=1;
        }
        return res;
    }
};

char str[256];
ll n;
int K;
int C[MAXK][MAXK];

int main(void){
    scanf("%lld%d",&n,&K);
    C[1][0]=C[1][1]=1;
    for(reg int i=2;i<=K;++i){
        C[i][0]=C[i][i]=1;
        for(reg int j=1;j<=i;++j)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
    }
    Matrix T(K+2,K+2);
    T.unit[0][0]=2,T.unit[1][0]=1;
    for(reg int i=1;i<=K;++i)
        for(reg int j=i;j<=K+1;++j)
            T.unit[j][i]=C[K-i+1][j-i];
    T.unit[K+1][K+1]=1;
    Matrix ans(1,K+2);
    for(reg int i=1;i<=K+1;++i)
        ans.unit[0][i]=1;
    Matrix X=T^(n-1);
    ans=ans*X;
    reg int ans1=ans.unit[0][0];
    ans=ans*T;
    reg int ans2=ans.unit[0][0];
    printf("%d\n",(ans2-ans1+MOD)%MOD);
    return 0;
}

解法 B（数论解法）

思路

不妨设
$$s _ i=\sum^n _ {i=1}a _ i$$

那么显然
$$s _ i=2s _ {i-1}+i^k$$

等式两边同时除以 $2^i$，构造数列 $\{a _ i\}$，则我们有
$$\begin{cases}a _ i=\frac{s _ i}{2^i}\\a _ i=a _ {i-1}+\frac{i^k}{2^i}\end{cases}$$

归纳可得
$$a _ i=\sum^i _ {j=1}\frac{j^k}{2^j}$$

不妨设
$$F _ i=\sum^i _ {j=1}\frac{j^k}{2^j}$$

进行变换
$$
\begin{aligned}
\frac{1}{2}F _ i&=F _ i-\frac{1}{2}F _ i\\
&=\sum^i _ {j=1}\frac{j^k}{2^j}-\sum^i _ {j=1}\frac{j^k}{2^{j+1}}\\
&=\sum^{i-1} _ {j=0}\frac{j^k}{2^{j+1}}-\sum^i _ {j=1}\frac{j^k}{2^{j+1}}\\
&=\sum^{i-1} _ {j=0}\frac{(j+1)^k}{2^{j+1}}-\sum^i _ {j=1}\frac{j^k}{2^{j+1}}\\
&=1-\sum^{i-1} _ {j=1}\frac{(j+1)^k-j^k}{2^{j+1}}-\frac{i^k}{2^{i+1}}\\
&=1-\sum^{i-1} _ {j=1}\frac{(j+1)^k-j^k}{2^{j+1}}-\frac{i^k}{2^{i+1}}\\
&=1-\sum^{i-1} _ {j=1}\frac{\sum^k _ {r=0}\binom{k}{r}j^r-j^k}{2^{j+1}}-\frac{i^k}{2^{i+1}}\\
&=1-\sum^{i-1} _ {j=1}\frac{\sum^{k-1} _ {r=0}\binom{k}{r}j^r}{2^{j+1}}-\frac{i^k}{2^{i+1}}\\
\end{aligned}
$$

解法 C（神仙解法）