[Medium] CF1997F Chips on a Line

xiezheyuan2025/1/28约 1031 字大约 5 分钟

提供一个不需要 Zeckendorf's Theorem 的做法。

简要题意

有一个游戏在数轴的区间 $[1,\infty)$ 上进行，每个整点上可能有一些筹码。你可以进行以下操作任意次：

选定一个 $i\in[1,\infty)$ ，移去 $i+1,i+2$ 两点上各一个筹码，然后在点 $i$ 放置一个筹码。
选定一个 $i\in[1,\infty)$ ，移去点 $i$ 上的各一个筹码，然后在点 $i+1,i+2$ 上各放置一个筹码。
将点 $1$ 上的一个筹码移动至点 $2$ 。
将点 $2$ 上的一个筹码移动至点 $1$ 。

你的得分是最终区间 $[1,\infty)$ 上的筹码总数。

现在总共有 $n$ 个筹码，你需要将其任意分配给 $[1,x]$ 中的任意个整点，使得你的得分最小值恰好为 $m$ ，求方案数，答案对 $998,244,353$ 取模。

$1\leq m\leq n\leq 10^3,2\leq x\leq 10$ 。

思路

看到题目后，可以发现两个事实：

操作是可逆的。
经过任意次操作，可以将所有筹码移动到点 $1$ 。

所以我们可以想到先将所有筹码移动到点 $1$ ，假设此时点 $1$ 上有 $a$ 个筹码。然后还原到某一个筹码数最少的状态，要求这个状态可以通过操作，使得所有的 $a$ 个筹码均在点 $1$ 。

因此，我们需要解决两个子问题：

对于一个状态，将所有筹码移动到点 $1$ 后，点 $1$ 上有多少个筹码。
可以通过操作，使得所有的 $a$ 个筹码均在点 $1$ 的状态中，筹码最少的状态是什么。

对于第一个问题，我们发现每个筹码是独立的，不妨设 $f(i)$ 表示位于点 $i$ 的筹码移动到点 $1$ 后变为多少个筹码。容易列出转移方程 $f(i)=f(i-1)+f(i-2)$ ，边界 $f(1)=f(2)=1$ 。这个 $f(n)$ 其实就是 Fibonacci 数列。于是假设所有筹码分别位于点 $a_1,a_2,\cdots,a_n$ ，则操作后点 $1$ 就有 $f(a_1)+f(a_2)+\cdots+f(a_n)$ 个筹码。

对于第二个问题，我们可以 dp，设 $\mathrm{vis}(i,j,k)$ 表示考虑到第 $i$ 个位置，放置了 $j$ 个筹码，当前状态下，将所有筹码移动到点 $1$ 后，点 $1$ 上有 $k$ 筹码，这种状态是否存在。转移就是一个完全背包状物。

至于 $i$ 的上界，由于 $f(25)>10^3\cdot f(10)$ ，所以取 $i\leq 24$ 即可。时间复杂度 $O(24f^2(n)n)$ 。

于是筹码数量的最小值就是最小的 $x$ 满足 $\mathrm{vis}(24,x,a)$ 。

然后考虑解决原问题，设 $f(i,j,k)$ 表示考虑到第 $i$ 个位置，放置了 $j$ 个筹码，当前状态下，将所有筹码移动到点 $1$ 后，点 $1$ 上有 $k$ 筹码的状态数。转移是类似的。，不过此时 $i$ 的上界是 $x$ ，最后简单统计一下即可。

时间复杂度 $O(24f^2(n)n)$ 。

代码

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

constexpr int mod = 998244353;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }

const int N = 1e3 + 5;
int n, x, m, fib[25], cnt[N * 55], f[N][55 * N];
bool vis[N][55 * N];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> x >> m;
    fib[1] = 1;
    for(int i=2;i<=24;i++) fib[i] = Add(fib[i - 1], fib[i - 2]);
    f[0][0] = 1;
    for(int i=1;i<=x;i++){
        for(int j=1;j<=n;j++){
            for(int k=fib[i];k<=fib[x]*n;k++) f[j][k] = Add(f[j][k], f[j - 1][k - fib[i]]);
        }
    }
    vis[0][0] = 1;
    for(int i=1;i<=24;i++){
        for(int j=1;j<=n;j++){
            for(int k=fib[i];k<=fib[x]*n;k++) vis[j][k] |= vis[j - 1][k - fib[i]];
        }
    }
    for(int i=1;i<=fib[x]*n;i++){
        for(int k=1;k<=n;k++){
            if(vis[k][i]){
                cnt[i] = k;
                break;
            }
        }
    }
    int ans = 0;
    for(int i=1;i<=fib[x]*n;i++){
        if(cnt[i] == m) ans = Add(ans, f[n][i]);
    }
    cout << ans << '\n';
    return 0;
}

// Written by xiezheyuan