LG5364 [SNOI2017] 礼物

摘要

这样一个规则: 第一个数为 \(1\), 后面的数为前面数之和 \(+i^k\). 求第 \(n\) 个数.

解

写出前几个贡献

\[1^k \]

\[1^k+2^k \]

\[1^k*2+2^k+3^k \]

\[1^k*4+2^k*2+3^k+4^k \]

有:

\[a_i=a_{i-1}*2-(i-1)^k+i^k \]

考虑 \(k\) 次幂如何递推:

\[(n+1)^k=\sum_{i=0}^k C_k^i n^{k-i} \]

\(k+1\) 个变量, 递推系数一定. 故我们可以矩阵维护 \(n\) 的 \(0\sim k\) 次幂, 预处理杨辉三角矩阵相乘得到 \(n+1\) 的 \(0\sim k\) 次幂.

我们可以进一步优化转移方程只维护一个次幂. 记前缀和 \(s_i\), 有:

\[s_i=2s_{i-1}+i^k \]

快速幂即可. 复杂度 \(\mathcal{O}(k^3\log{n})\).

代码

#include
#include
#define rep(i,a,b) for(int i=(a);i<=(b);++i)

typedef long long ll;
const int M=15,mod=1e9+7;
int m;
ll n;

struct mat
{
	ll a[15][15];
	mat(){memset(a,0,sizeof(a));}
	ll*operator[](int x)
		{return a[x];}
	friend mat operator*(mat l,mat r)
	{
		mat x;
		rep(k,0,m+1)
			rep(i,0,m+1)
				rep(j,0,m+1)
					(x[i][j]+=l[i][k]*r[k][j])%=mod;
		return x;
	}
}t;

mat qpow(mat x,ll p)
{
	mat res;
	rep(i,0,m+1)
		res[i][i]=1;
	while(p)
	{
		if(p&1)
			res=res*x;
		x=x*x,p>>=1;
	}
	return res;
}

int main()
{
	scanf("%lld%d",&n,&m);
	rep(j,0,m)
	{
		t[0][j]=t[j][j]=1;
		rep(i,1,j-1)
			t[i][j]=(t[i-1][j-1]+t[i][j-1])%mod;
	}
	t[m+1][m+1]=2,t[m][m+1]=1;
	mat ans;
	rep(i,0,m)
		ans[0][i]=1;
	printf("%d\n",((ans*qpow(t,n))[0][m+1]-(ans*qpow(t,n-1))[0][m+1]+mod)%mod);
	return 0;
}