传送门

Solution

设 fibifib_i 为斐波那契数列的第 ii 项，cic_i 为第 ii 格的芯片数，那么当所有 cic_i 确定时，无论怎么操作，都能保证 k=∑fibicik=\sum fib_ic_i 不变。因此所有情况都可以变成在第一格上放置若干个芯片，其它格子上没有芯片。

设 gig_i 为第一格有 ii 个芯片，经过操作后，最少剩下多少芯片。求解 gig_i 可以类比为完全背包求能获得的最小价值。

设 fj,kf_{j,k} 表示 ∑ci=j\sum c_i=j，∑fibici=k\sum fib_ic_i=k 的 cc 的数量。同样通过完全背包求解。

dp 最外层不能是 jj 的原因是会算重。

答案为将所有符合 gk=mg_k=m 的 fn,kf_{n,k} 相加。

时间复杂度为 O(n2x⋅fibx)O(n^2x\cdot fib_x)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 55005, mod = 998244353;

ll n, x, m, g[N], f[1005][N], tot, fab[N], ans;

int main()
{
	scanf("%lld%lld%lld", &n, &x, &m);
	fab[1] = 1;
	for (int i = 2; i <= 24; i++)
		fab[i] = fab[i - 1] + fab[i - 2];
	tot = n * fab[x];
	memset(g, 0x3f, sizeof(g));
	g[0] = 0;
	for (int i = 1; i <= 24; i++)
		for (int j = fab[i]; j <= tot; j++)
			g[j] = min(g[j], g[j - fab[i]] + 1);
	f[0][0] = 1;
	for (int i = 1; i <= x; i++)
		for (int j = 1; j <= n; j++)
			for (int k = fab[i]; k <= tot; k++)
				f[j][k] = (f[j][k] + f[j - 1][k - fab[i]]) % mod;
	for (int i = n; i <= tot; i++)
		if (g[i] == m)
			ans = (ans + f[n][i]) % mod;
	printf("%lld", ans);
	return 0;
}