ACM暑假训练 中石油oj 3737: 礼物（矩阵快速幂）

3737: 礼物

时间限制: 5 Sec  内存限制:512 MB

提交: 46  解决: 12

[提交][状态][讨论版]

题目描述

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

输入

第一行，两个整数 N,K。

输出

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

样例输入

4 2

样例输出

37

提示

100% 的数据：N≤10¹⁸，K≤10。

【解析】：

由题意可以看出：an = S(n-1) + n^k ；

数据量太大，直接递推会超时。

所以用这个递推式，构造矩阵，然后利用矩阵快速幂，从而将时间复杂度从O(n)降到O(log n)

利用二项式分解n^k可得：

（注意注意： Sn = S(n-1) + an）

然后设两个矩阵Xn和Xn+1，令他们：

那么一定存在这样的矩阵A。

手算构造这个矩阵A。其中多次用到二项式分解。

特别注意区分Sn和an

构造结果：

然后，X(n+1) = A * Xn;

则 Xn = A^(n-2) * X2；

A^(n-2)通过矩阵快速幂秒求，然后直接通过X2推出Xn

【代码】：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
struct zhen{
	int r,c;//行列始于1
	ll a[16][16];
	zhen(int R=0,int C=0){
		memset(a,0,sizeof(a));
		r=R;c=C;
	}
};
ll Cf[15][15];//组合数打表
zhen operator*(zhen A,zhen B)//矩阵A*B
{
	zhen C(A.r,B.c);
	for(int i=1;i<=A.r;i++)
		for(int j=1;j<=B.c;j++)
			for(int k=1;k<=A.c;k++){
				C.a[i][j]+=(A.a[i][k]*B.a[k][j])%mod;
				C.a[i][j]%=mod;
			}
	return C;
}
zhen qpow(zhen A,ll m)//方阵A的m次幂
{
	zhen ans(A.r,A.c);
	for(int i=1;i<=A.r;i++) ans.a[i][i]=1;//单位矩阵
	while(m)
	{
		if(m%2)ans=ans*A;
		A=A*A;
		m/=2;
	}
	return ans;
}
ll qpow(ll n,ll m)
{
	n%=mod;
	ll ans=1;
	while(m) 
    {  
        if(m%2)  
            ans=(ans*n)%mod;  
        m/=2;  
        n=(n*n)%mod;
    } 
    return ans;
}
void output(zhen A)
{
	for(int i=1;i<=A.r;i++){
		for(int j=1;j<=A.c-1;j++)
			cout<<A.a[i][j]<<' ';
		cout<<A.a[i][A.c]<<endl;
	}
}
void init()//组合数打表 
{
	Cf[0][0]=1;//特殊
	for(int i=1;i<=13;i++)
		for(int j=0;j<=i;j++)
			Cf[i][j]=(j==0)?1:(Cf[i-1][j]+Cf[i-1][j-1])%mod;
}
int main()
{
	init();//初始化组合数
	ll n,k;
	cin>>n>>k;
	if(n==1){
		puts("1");return 0;
	}
	
	zhen A(k+2,k+2);//构造矩阵A
	A.a[1][1]=2;
	for(int i=2;i<=A.c;i++)//第一二行
		A.a[2][i]=A.a[1][i]=Cf[k][i-2];
	for(int i=3;i<=A.r;i++)//三行往后
		for(int j=i;j<=A.c;j++){
			A.a[i][j]=Cf[A.r-i][j-i];
		}
	//矩阵A构造完毕
	//所以 Xn = A^(n-2) * X2;
	zhen X2(A.r,1),Xn;
	for(int i=1;i<=X2.r;i++)
		X2.a[i][1]=1;
	Xn=qpow(A,n-2)*X2;
	ll ans=Xn.a[1][1]+qpow(n,k);//an = S(n-1) + n^k
	cout<<ans%mod<<endl;
}

矩阵快速幂解决递推题 推荐博文：点击打开链接

要点：将an利用二项式展开，要含有n-1