Magic Gems

NC230081. Magic Gems

描述

Reziba 有很多魔法宝石。每颗魔法宝石可以分解成 $m$ 颗普通宝石，魔法宝石和普通宝石都占据 $1$ 体积的空间，但普通宝石不能再被分解。

Reziba 想要使一些魔法宝石分解，使得所有宝石占据的空间恰好为 $n$ 单位体积。显然，一个魔法宝石分解后会占据 $m$ 体积空间，不分解的魔法宝石仍占据 $1$ 体积空间。

现在 Reziba 想要求出有多少种分解方案，可以让最后得到的宝石恰好占据 $n$ 单位体积。两种分解方案不同当且仅当分解的魔法宝石数量不同，或者是所用的宝石的编号不同。

Reziba 当然知道怎么做，但是他想考考你。

输入描述

输入包含两个数字

输出描述

输出能使宝石占据恰好  体积的方案数。因为方案数实在太大了，请输出方案数  后的结果。

示例1

输入:

4 2

输出:

说明:

该样例中一颗魔法宝石可以分解得到两颗普通宝石，我们的目标是拿到 $4$ 颗魔法宝石。

让我们用 $1$ 代表魔法宝石， $0$ 代表普通宝石。

则存在如下几种方案：

* $1111$ ：没有宝石被分解。
* $0011$ ：第一颗宝石分解。
* $1001$ ：第二颗宝石分解。
* $1100$ ：第三颗宝石分解。
* $0000$ ：第一颗和第二颗宝石分解。

因此答案为 $5$

示例2

输入:

3 2

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 603ms, 内存消耗: 732K, 提交时间: 2022-03-12 11:32:08

#include<bits/stdc++.h>
using namespace std;
int m, mo=1e9+7;
long long n, f[105][105], a[105][105];
void mul(long long a[105][105], long long b[105][105]){
	long long c[105][105]={0};
	for(int i=1; i<=m; i++){
		for(int j=1; j<=m; j++){
			for(int k=1; k<=m; k++){
				c[i][j]+=a[i][k]*b[k][j]%mo;
			}
			c[i][j]%=mo;
		}
	}
	memcpy(b, c, sizeof(c));
}
int main(){
	scanf("%lld%d", &n, &m);
	if(n<m){
		printf("1");
		return 0;
	}
	for(int i=2; i<=m; i++) f[i][1]=a[i][i-1]=1;
	f[1][1]=2, a[1][1]=a[1][m]=1, n-=m;
	while(n){
		if(n&1) mul(a, f);
		mul(a, a), n>>=1;
	}
	printf("%lld", f[1][1]);
	return 0;
}

上一题

下一题

详情