BZOJ_5015_[Snoi2017]礼物_矩阵乘法
Description
热情好客的请森林中的朋友们吃饭，他的朋友被编号为 1～N，每个到来的朋友都会带给他一些礼物：。其中，第
一个朋友会带给他 1 个，之后，每一个朋友到来以后，都会带给他之前所有人带来的礼物个数再加他的编号的 K
次方那么多个。所以，假设 K=2，前几位朋友带来的礼物个数分别是：1,5,15,37,83假设 K=3，前几位朋友带来的
礼物个数分别是：1,9,37,111现在，好奇自己到底能收到第 N 个朋友多少礼物，因此拜托于你了。已知 N,K请输
出第 N 个朋友送的礼物个数 mod1000000007。
Input
第一行，两个整数 N,K
N≤10^18,K≤10
Output
一个整数，表示第 N 个朋友送的礼物个数 mod1000000007。
Sample Input
4 2
Sample Output
37
设序列的前缀和为$S_n$,$S_n=S_{n-1}+n^{k}$。
$(S_{n-1}; n^{k}; ...n^{0})$ -> $(S_{n};(n+1)^{k};...(n+1)^{0})$
转移矩阵发现可以用二项式定理。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
typedef long long ll;
int m;
ll n,mod=1000000007,c[15][15];
struct Mat {
ll v[14][14];
Mat(){memset(v,0,sizeof(v));}
Mat operator*(const Mat &x)const {
Mat re;int i,j,k;
for(i=1;i<=m;i++) {
for(j=1;j<=m;j++) {
for(k=1;k<=m;k++) {
(re.v[i][j]+=v[i][k]*x.v[k][j]%mod)%=mod;
}
}
}
return re;
}
};
void print(Mat x) {
int i,j;
for(i=1;i<=m;i++) {
for(j=1;j<=m;j++) {
printf("%lld ",x.v[i][j]);
}
puts("");
}
}
Mat qp(Mat x,ll y) {
Mat I;
int i;
for(i=1;i<=m;i++) I.v[i][i]=1;
while(y) {
if(y&1ll) I=I*x;
x=x*x;
y>>=1ll;
}
return I;
}
Mat build() {
Mat x;
int i,j;
x.v[1][1]=2; x.v[2][1]=1;
for(i=2;i<=m;i++) {
int k=m-i+1;
for(j=0;j<=k;j++) {
x.v[j+i][i]=c[k-1][j];
}
}
/*for(i=1;i<=m;i++) {
for(j=1;j<=m;j++) {
printf("%lld ",x.v[i][j]);
}
puts("");
}*/
return x;
}
void init() {
int i,j;
for(i=0;i<=m;i++) c[i][0]=c[i][i]=1;
for(i=1;i<=m;i++) {
for(j=1;j<=m;j++) {
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
}
}
int main() {
scanf("%lld%d",&n,&m); m+=2;
init();
Mat A;
int i;
for(i=2;i<=m;i++) A.v[1][i]=1;
Mat x=build();
Mat T=A*qp(x,n-1);
//print(T);
printf("%lld
",((T*x).v[1][1]-T.v[1][1]+mod)%mod);
}