SNOI2017 D1T1 神仙题目。
（未完待续）
题目链接：Luogu P5364/LibreOJ 2253/SNOI2017 D1T1。
题目
题目描述
热情好客的小猴子请森林中的朋友们吃饭，他的朋友被编号为 $1\sim N$，每个到来的朋友都会带给他一些礼物：大香蕉。其中，第一个朋友会带给他 $1$ 个大香蕉，之后，每一个朋友到来以后，都会带给他之前所有人带来的礼物个数再加他的编号的 $K$ 次方那么多个。
现在，小猴子好奇自己到底能收到第 $N$ 个朋友多少礼物，因此拜托于你了，结果对 $10^9+7$ 取模。
数据范围
| 变量 | 数据范围 |
|---|---|
| $N$ | $\leq 10^{18}$ |
| $k$ | $\leq 10$ |
时空限制
| 题目编号 | 时间限制 | 空间限制 |
|---|---|---|
| Luogu P5364 | ||
| LibreOJ 2253 | ||
| SNOI2017 D1T1 |
题解
本题有多种做法，下面介绍一些正解。
事先约定：用 $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}
$$
近期评论