loj2253 「SNOI2017」礼物

对于一个在位置 \(i\) 的数，他等于 \(i^k+sum_{1,k-1}\)。

二项式定理推 \(i^k\)，矩阵快速幂即可。

#include <iostream>

#include <cstdio>

using namespace std;

typedef long long ll;

int k, c[15][15];

ll n;

const int mod=1e9+7;

struct Matrix{

	int num[15][15];

	Matrix operator*(const Matrix &x)const{

		Matrix re;

		for(int i=0; i<=k+1; i++)

			for(int j=0; j<=k+1; j++){

				re.num[i][j] = 0;

				for(int l=0; l<=k+1; l++)

					re.num[i][j] = (re.num[i][j] + (ll)num[i][l]*x.num[l][j]) % mod;

			}

		return re;

	}

}yua, zhu, dan;

Matrix ksm(ll b){

	while(b){

		if(b&1)	dan = dan * zhu;

		zhu = zhu * zhu;

		b >>= 1;

	}

	return dan;

}

int main(){

	cin>>n>>k;

	for(int i=0; i<=k; i++)

		yua.num[0][i] = dan.num[i][i] = 1;

	c[0][0] = zhu.num[k][k+1] = dan.num[k+1][k+1] = 1;

	for(int i=1; i<=k; i++){

		c[i][0] = 1;

		for(int j=1; j<=i; j++)

			c[i][j] = (c[i-1][j] + c[i-1][j-1]) % mod;

	}

	for(int i=0; i<=k; i++)

		for(int j=i; j<=k; j++)

			zhu.num[i][j] = c[j][i];

	zhu.num[k+1][k+1] = 2;

	Matrix ans=yua*ksm(n-1);

	cout<<(ans.num[0][k+1]+ans.num[0][k])%mod<<endl;

	return 0;

}

巴特西

loj2253 「SNOI2017」礼物

最新文章

热门文章