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}
$$
近期评论