[洛谷 5364,loj 2253][SNOI2017]礼物

题目链接

https://www.luogu.com.cn/problem/P5364

https://loj.ac/problem/2253

题解

乍一看似乎没啥思路,我们来找找规律。

先是第 \(i\) 个数的规律。表格中是各项系数的值。

\(1^k\) \(2^k\) \(3^k\) \(4^k\) \(5^k\)
1 1
2 1 1
3 2 1 1
4 4 2 1 1
5 8 4 2 1 1

看起来有些规律,不过似乎不太好表示。

让我们把前 \(i\) 项的和表示一下吧。

\(1^k\) \(2^k\) \(3^k\) \(4^k\) \(5^k\)
1 1
2 2 1
3 4 2 1
4 8 4 2 1
5 16 8 4 2 1

到这里似乎豁然开朗了。前 \(i+1\) 项的和,在前 \(i\) 项的和的基础上乘二,并添加了一个新项。

设前 \(i\) 项的和为 \(S_i\),易知:

$$S_i=2S_{i-1}+i^k$$

考虑用矩阵快速幂来加速递推。

原式中的 \(i^k\) 不太好处理,这时候需要用到一点二项式定理的知识来解决。

将 \((i+1)^k\) 展开:

$$(i+1)^k=\sum_{p=0}^k C_k^p i^p$$

从而我们就将 \((i+1)^k\) 拆分成了若干个 \(i^p\) 相加的形式。

在转移矩阵中维护 \(i^0 \sim i^k\) 以及 \(S_i\),就可以以 \(O(k^3 \log n)\) 的时间复杂度通过此题。

#include <cstring>
#include <iostream>
#define MOD 1000000007
using namespace std;
long long n,k;
struct mat
{
 long long a[15][15];
 mat(int x=0)
 {
  memset(a,0,sizeof(a));
  for(int i=0;i<=k;i++)
   a[i][i]=x;
 }
 mat operator*(const mat&b)const
 {
  mat ans;
  for(int l=0;l<=k+1;l++)
   for(int i=0;i<=k+1;i++)
    for(int j=0;j<=k+1;j++)
     ans.a[i][j]=(ans.a[i][j]+a[i][l]*b.a[l][j])%MOD;
  return ans;
 }
}f,g;
void init()
{
 //[n^0,n^1,...,n^k,s_0]
 for(int i=0;i<=k;i++)
  f.a[0][i]=1;
 for(int i=0;i<=k;i++)
  g.a[0][i]=1;
 for(int i=1;i<=k;i++)
  for(int j=1;j<=k;j++)
   g.a[i][j]=g.a[i-1][j-1]+g.a[i][j-1];
 g.a[k][k+1]=1,g.a[k+1][k+1]=2;
}
mat fpow(mat x,long long y)
{
 mat ans(1);
 while(y)
 {
  if(y&1)ans=ans*x;
  x=x*x;
  y>>=1;
 }
 return ans;
}
int main()
{
 cin>>n>>k;
 init();
 long long res1=(f*fpow(g,n)).a[0][k+1],res2=(f*fpow(g,n-1)).a[0][k+1];
 cout<<(res1-res2+MOD)%MOD<<endl;
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据