Educational Codeforces Round 60 D dp + 矩阵快速幂

https://codeforces.com/contest/1117/problem/D

题意

有n个特殊宝石(n<=1e18),每个特殊宝石可以分解成m个普通宝石(m<=100),问组成n颗宝石有多少种方法

题解

数据很大：找规律or矩阵快速幂
转移方程: dp[i]=dp[i-1]+dp[i-m]
因为n<=1e18可以用矩阵快速幂
构造矩阵如图:

\[\left[
\begin{matrix}
f[i-1] & f[i-2] & \cdots & f[i-m] \\
\end{matrix}
\right]
*
\left[
\begin{matrix}
1 & 1 &0 & \cdots & 0 \\
0 & 0 &1 & \cdots & 0 \\
\vdots & \vdots &\vdots &\ddots & \vdots \\
0 & 0 &0 &\cdots & 1 \\
1 & 0 &0 &\cdots & 0 \\
\end{matrix}
\right]
=
\left[
\begin{matrix}
f[i] & f[i-1] & \cdots & f[i-m+1] \\
\end{matrix}
\right]
\]

代码(矩阵快速幂板子)

#include<bits/stdc++.h>

#define P 1000000007

#define ll long long

#define M 105

using namespace std;

struct N{

	ll a[M][M];

};

ll m,n,i,j;

N mul(N x,N y){

	N z;

	memset(z.a,0,sizeof(z.a));

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

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

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

				z.a[i][j]+=x.a[i][k]*y.a[k][j]%P;

				z.a[i][j]%=P;

			}

	return z;

}

N pw(N bs,ll x){

	N y;

	memset(y.a,0,sizeof(y.a));

	for(int i=1;i<=n;i++)y.a[i][i]=1;

	while(x){

		if(x&1)y=mul(y,bs);

		bs=mul(bs,bs);

		x>>=1;

	}

	return y;

}

int main(){

	cin>>m>>n;

	N f;memset(f.a,0,sizeof(f.a));

	f.a[1][1]=1;f.a[n][1]=1;

	for(i=1,j=2;j<=n;j++,i++)f.a[i][j]=1;

	f=pw(f,m);

	cout<<f.a[1][1]%P;

}

巴特西

Educational Codeforces Round 60 D dp + 矩阵快速幂

最新文章

热门文章