CF1117D Magic Gems

2019/02/19 09:54
阅读数 64

CF1117D Magic Gems

  • 考虑 $dp$ , $f[i]$ 表示用 $i$ 个单位空间的方案数,答案即为 $f[n]$.
  • 对于一个位置,我们可以放 $Magic$ 的,占 $m$ 空间,也可以放 $Normal$ 的,占 $1$ 空间.
  • 转移方程即为 $f[i]=f[i-1]+f[i-m]$ ,边界条件为 $f[0]=f[1]=f[2]=\dots f[m-1]=1$.
  • 直接转移是 $O(n)$ 的,无法通过,需要矩阵优化.

  • 时间复杂度为 $O(m^3logn)$ ,可以通过本题.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
inline ll read()
{
	ll x=0;
	bool pos=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar())
		if(ch=='-')
			pos=0;
	for(;isdigit(ch);ch=getchar())
		x=x*10+ch-'0';
	return pos?x:-x;
}
const int MAXM=110;
const int P=1e9+7;
inline int add(int a,int b)
{
	return (a + b) % P;
}
inline int mul(int a,int b)
{
	return 1LL * a * b % P;
}
ll n;
int m;
struct Matrix{
	int a[MAXM][MAXM];
	Matrix()
		{
			for(int i=1;i<=m;++i)	
				for(int j=1;j<=m;++j)
					a[i][j]=0;
		}
	Matrix operator * (const Matrix &rhs) const	
		{
			Matrix res;
			for(int k=1;k<=m;++k)
				for(int i=1;i<=m;++i) if(a[i][k])
					for(int j=1;j<=m;++j) if(rhs.a[k][j])
						res.a[i][j]=add(res.a[i][j],mul(a[i][k],rhs.a[k][j]));
			return res;
		}
};
Matrix fpow(Matrix x,ll b)
{
	Matrix res;
	for(int i=1;i<=m;++i)
		res.a[i][i]=1;
	while(b)
		{
			if(b&1)
				res=res*x;
			x=x*x;
			b>>=1;
		}	
	return res;
}
int main()
{
	n=read(),m=read();
	if(n<m)
		return puts("1")&0;
	Matrix st;//st_{m-1}
	for(int i=1;i<=m;++i)
		st.a[i][1]=1;
	Matrix trans;
	trans.a[1][1]=trans.a[1][m]=1;
	for(int i=2;i<=m;++i)
		trans.a[i][i-1]=1;
	st=fpow(trans,1LL*(n-m+1))*st;
	cout<<st.a[1][1];
	return 0;
}
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部