【SNOI2017 DAY1】礼物

Problem

传送门

定位：二项式定理+矩阵乘法

设\(S_i=A_1+A_2+...+A_i\)
则\(A_i=S_{i-1}+i^K,S_i=S_{i-1}+A_i=2S_{i-1}+i^K\)

发现，这是一个递推式，而\(n \leq 10^{18}\)，不难想到用矩阵去优化转移。

现在难点在于\((i+1)^K\)如何通过\(i\)转移而来，不难通过二项式定理
\((i+1)^K=\sum C_{n-k}^{k} i^k \times 1^{n-k}\)
所以可以构造出一下矩阵：

\[\begin{gathered} \begin{pmatrix} S_i & n^K & n^{K-1} & n^{K-2} & ... & n^0 \end{pmatrix} \quad \end{gathered} \times \begin{gathered} \begin{pmatrix} 2 & 0 & 0 & 0 & 0 & ...\\ 0 & C & 0 & 0 & 0 & ...\\ 0 & C & C & 0 & 0 & ...\\ ... & \\ \end{pmatrix} \quad \end{gathered} \]

C代指二项式定理各项系数（其实就是杨辉三角）

\(code:\)

#include
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
int N;
struct Matrix{
	ll x[12][12];
	Matrix(){for(int i=0;i>=1;
	}
	return res;
}
int main(){
	cin>>n>>k;
	N=k+2;
	for(int i=1;i=1;i--){
		B.x[N-1][i]=1;
		for(int j=N-2;j>=i;j--)
			B.x[j][i]=B.x[j+1][i+1]+B.x[j][i+1];
	}
	A=A*ksm(B,n-1);
	Matrix C=A*B;
	printf("%lld\n",(C.x[0][0]-A.x[0][0]+mod)%mod);
	return 0;
}