CF1117D Magic Gems dp 매트릭스 곱셈

제목 링크
제목: 당신은 마력이 있는 보석을 임의로 여러 개 가지고 있습니다. 마력이 있는 보석은 m m m의 일반 보석으로 분열할 수 있습니다. 보석이 차지하는 공간은 111입니다. nn의 공간을 채우는 방안이 몇 가지가 있는지 물어보세요.n < = 1 e 18 , m < = 100 n<=1e18,m<=100 n<=1e18,m<=100.
문제풀이: 당시 시합할 때 만들지 못하고 주문이 있었어요.주로 이걸 할 때 시간이 부족해서 잘못된 길로 들어서서 조합수로 하려고 했는데 그게 안 된다는 걸 알고 자폐를 했어요.
이런 숫자 문제는 조합수를 풀 수 없는 상황에서 dp를 먼저 고려해야 한다.우리는 dp[i]를 설정하여 마지막으로 ii의 공간을 차지하는 방안 수를 나타낸다.우리는 마지막 마법 보석을 직접 넣을지 mm개로 분열할지 다음과 같은 이동이 있다. dp[i]=dp[i-3-1]+dp[i-3]dp[i]=dp[i-1]+dp[i-m]dp[i]=dp[i]=dp[i-3]+dp[i-3]]+dp[i-3]]m]
위의 dp식이 있으면 우리는 O(n)O(n)O(n)O(n)의 시간 안에 이 문제를 해결할 수 있지만 n=1e18n=1e18n=1e18n=1e18n=1e18은 이 문제를 통과할 수 없다.우리는 이 식이 하나의 점차적인 식으로 행렬 곱셈으로 최적화할 수 있음을 발견했다. 그리고 여기서 m<=100m<=100m<=100m<=100, 시공 복잡도가 허용되어 행렬을 구성할 수 있다.
우리는 두 행렬이 기록한 양 간의 관계를 고려하여 어떻게 이동했는지 기록한다.
[ d p [ n − m − 1 ] d p [ n − m ] . . . d p [ n − 1 ] ] ∗\begin{bmatrix} dp[n-m-1] & dp[n-m] & ... & dp[n-1]\end{bmatrix}* [dp[n−m−1]​dp[n−m]​...dp[n-1] 전이 행렬 = [dp [n-3m] dp [n-3m + 1].d p [ n ] ] =\begin{bmatrix} dp[n-m] & dp[n-m+1] & ... & dp[n]\end{bmatrix} =[dp[n−m]​dp[n−m+1]​...​dp[n]​]
사고 과정은 쓰지 말고 이동 행렬을 직접 써라.
[ d p [ n − m − 1 ] d p [ n − m ] . . . d p [ n − 1 ] ] ∗ [ 0 0 0 . . . 0 1 1 0 0 . . . 0 0 0 1 0 . . . 0 0 0 0 1 . . . 0 0 . 0 0 . . . 0 0 . 0 0 . . . 0 0 . 0 0 . . . 0 0 0 0 0 . . . 1 1 ] = [ d p [ n − m ] d p [ n − m + 1 ] . . . d p [ n ] ]\begin{bmatrix} dp[n-m-1] & dp[n-m] & ... & dp[n-1]\end{bmatrix}*\begin{bmatrix} 0 & 0 & 0 & ...&0 & 1\\1 & 0 & 0 & ...& 0 &0\\0 & 1 & 0 & ...& 0 &0\\0 & 0 & 1 & ...& 0 &0\\. & 0 & 0 & ...& 0 &0\\. & 0 & 0 & ...& 0 &0\\. & 0 & 0 & ...& 0 & 0\\0 & 0 & 0 & ...&1 & 1\\\end{bmatrix}=\begin{bmatrix} dp[n-m] & dp[n-m+1] & ... & dp[n]\end{bmatrix} [dp[n−m−1]​dp[n−m]​...​dp[n−1]​]∗⎣⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎡​0100...0​00100000​00010000​........................​00000001​10000001​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎤​=[dp[n−m]​dp[n−m+1]​...​dp[n]​]
대체로 행렬은 이렇게 생겼죠. 어차피 행렬 곱셈을 할 줄 아는 스스로 구성하는 것도 어렵지 않아요.그래서 O(m 3 l o g n) O(m^3 logn) O(m3 logn)를 통과할 수 있습니다.
코드:

#include 
using namespace std;

int m;
long long n,a[110][110],ans[110][110],fz[110][110];
const long long mod=1e9+7;
inline void ans_jc()
{
	for(int i=1;i<=1;++i)
	{
		for(int j=1;j<=m;++j)
		{
			fz[i][j]=ans[i][j];
			ans[i][j]=0;
		}
	}
	for(int i=1;i<=1;++i)
	{
		for(int j=1;j<=m;++j)
		{
			for(int k=1;k<=m;++k)
			ans[i][j]=(ans[i][j]+fz[i][k]*a[k][j]%mod)%mod;
		}
	}
}
inline void x_jc()
{
	for(int i=1;i<=m;++i)
	{
		for(int j=1;j<=m;++j)
		{
			fz[i][j]=a[i][j];
			a[i][j]=0;
		}
	}
	for(int i=1;i<=m;++i)
	{
		for(int j=1;j<=m;++j)
		{
			for(int k=1;k<=m;++k)
			a[i][j]=(a[i][j]+fz[i][k]*fz[k][j]%mod)%mod;
		}
	}
}
inline void ksm(long long x)
{
	while(x)
	{
		if(x&1)
		ans_jc();
		x_jc();
		x>>=1;
	}
}
int main()
{
	scanf("%I64d%d",&n,&m);
	if(n<m)
	{
		cout<<1<<endl;
		return 0;
	}
	for(int i=1;i<=m;++i)
	ans[1][i]=1;
	ans[1][m]=2;
	for(int i=2;i<=m;++i)
	a[i][i-1]=1;
	a[1][m]=1;
	a[m][m]=1;
	ksm(n-m);
	printf("%I64d
",ans[1][m]);
	return 0;
}