【bzoj5015】[Snoi2017]礼物 矩阵乘法

题目描述

热情好客的请森林中的朋友们吃饭，他的朋友被编号为 1～N，每个到来的朋友都会带给他一些礼物：。其中，第一个朋友会带给他 1 个，之后，每一个朋友到来以后，都会带给他之前所有人带来的礼物个数再加他的编号的 K 次方那么多个。所以，假设 K=2，前几位朋友带来的礼物个数分别是：1,5,15,37,83假设 K=3，前几位朋友带来的礼物个数分别是：1,9,37,111现在，好奇自己到底能收到第 N 个朋友多少礼物，因此拜托于你了。已知 N,K请输出第 N 个朋友送的礼物个数 mod1000000007。

输入

第一行，两个整数 N,K

N≤10^18,K≤10

输出

一个整数，表示第 N 个朋友送的礼物个数 mod1000000007。 

样例输入

4 2

样例输出

37

---

题解

矩阵乘法

设前$i$项的和为$S_i$，那么根据定义有$a_n=S_{n-1}+n^k$，故有$S_n=S_{n-1}+a_n=2S_{n-1}+n^k$。

由于k不大，显然这个式子可以矩乘。

具体方法：维护矩阵$\begin{bmatrix}S_{n-1}&n^k&n^{k-1}&...&n^1&n^0\end{bmatrix}$，那么$S$的转移矩阵就是上面的式子，而$n^i$的转移矩阵就是二项式系数，即$(n+1)^i$的展开式。

于是矩阵乘法加速递推，最终的答案就是$S_n-S_{n-1}$。

时间复杂度$O(k^3\log n)$

#include <cstdio>

#include <cstring>

#include <algorithm>

#define mod 1000000007

using namespace std;

typedef long long ll;

int d;

struct data

{

	ll v[12][12];

	ll* operator[](int a) {return v[a];}

	data() {memset(v , 0 , sizeof(v));}

	data operator*(data a)

	{

		data ans;

		int i , j , k;

		for(i = 0 ; i <= d + 1 ; i ++ )

			for(j = 0 ; j <= d + 1 ; j ++ )

				for(k = 0 ; k <= d + 1 ; k ++ )

					ans[i][j] = (ans[i][j] + v[i][k] * a[k][j]) % mod;

		return ans;

	}

}A , P;

data pow(data x , ll y)

{

	data ans;

	int i;

	for(i = 0 ; i <= d + 1 ; i ++ ) ans[i][i] = 1;

	while(y)

	{

		if(y & 1) ans = ans * x;

		x = x * x , y >>= 1;

	}

	return ans;

}

int main()

{

	ll n;

	int i , j;

	scanf("%lld%d" , &n , &d);

	for(i = 1 ; i <= d + 1 ; i ++ ) A[0][i] = 1;

	P[0][0] = 2 , P[1][0] = 1;

	for(i = d + 1 ; i ; i -- )

	{

		P[d + 1][i] = 1;

		for(j = d ; j >= i ; j -- ) P[j][i] = P[j + 1][i + 1] + P[j][i + 1];

	}

	A = A * pow(P , n - 1);

	printf("%lld\n" , ((A * P)[0][0] - A[0][0] + mod) % mod);

	return 0;

}