题目
题解
定义 $N$ 的 Fibonacci 表示 $a_i$：
$$N = \sum a_if_i$$
其中 $f_i$ 为 Fibonacci 数，$f_1 = f_2 = 1$。注意 Fibonacci 表示可能不唯一。
有两个性质：所有操作可撤销 和 所有操作不改变 Fibonacci 表示下的和（$\sum a_if_i$）。
首先想想一个放置方案的 cost 是多少。找到 $\sum a_i$ 最小的 Fibonacci 表示，cost 就是 $\sum a_i$。这个表示显然可以从大到小枚举 Fibonacci 数贪心求解，且是唯一的。这个最小表示名为 Zeckendorf 表示。
那现在知道 cost 怎么算之后，我们可以判定出哪些数是需要统计进答案的了。
对于一个数来说，我们想计算有多少种不同的 Fibonacci 表示。设 $f_{i, j, k}$ 表示如果只用前 $i$ 个位，$\sum a_i = j$ 且 $\sum a_if_i = k$ 的方案数。
然后空间会卡，把第一维滚掉。
时间复杂度 $O\left(x \cdot n^2 \cdot f_x\right)$。
代码
/* C++17 is required!
* By Koicy (https://koicy.ly)
* Email n@rbtr.ee
* I've reached the end of my fantasy.
__ __ __ _
_____/ /_ / /_________ ___ / /______ (_)______ __
/ ___/ __ \/ __/ ___/ _ \/ _ \ ______ / //_/ __ \/ / ___/ / / /
/ / / /_/ / /_/ / / __/ __/ /_____/ / ,< / /_/ / / /__/ /_/ /
/_/ /_.___/\__/_/ \___/\___/ /_/|_|\____/_/\___/\__, /
SIGN /___*/
#ifndef XCODE
constexpr bool _CONSOLE = false;
#else
constexpr bool _CONSOLE = true;
#endif
#define __NO_MAIN__ false
#define __ENABLE_RBLIB__ true
constexpr bool _MTS = false, SPC_MTS = false;
constexpr char EFILE[] = "";
#define FULL(arg) arg.begin(), arg.end()
// :/
signed STRUGGLING([[maybe_unused]] unsigned long TEST_NUMBER) {
constexpr tp mod = 998244353;
tp n, x, m; bin >> n >> x >> m;
vetp fib { 0, 1, 1 };
for (tp i = 3; i <= 100; ++i) fib.push_back(fib[i - 1] + fib[i - 2]);
auto Zeckendorf = [&](tp n) -> tp {
tp ret = 0;
for (tp i = 100; i >= 1; --i) {
ret += n / fib[i];
n %= fib[i];
}
return ret;
};
vector<vetp> f(n + 1, vetp(fib[x] * n + 1));
f[0][0] = 1;
auto mad = [](tp a, tp b) { return a + b >= mod ? a + b - mod : a + b; };
for (tp i = 1; i <= x; ++i) {
for (tp j = 1; j <= n; ++j) {
for (tp k = fib[i]; k < f[j].size(); ++k) {
f[j][k] = mad(f[j][k], f[j - 1][k - fib[i]]);
}
}
}
tp tar = 0;
for (tp j = 1; j < f[n].size(); ++j) {
if (Zeckendorf(j) == m) tar = mad(tar, f[n][j]);
}
bin << tar << '\n';
return 0;
}
void MIST() {
}
// :\ */