CF1997F Chips on a Line

传送门

Solution

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

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

设 $f_{j,k}$ 表示 $\sum c_i=j$，$\sum fib_ic_i=k$ 的 $c$ 的数量。同样通过完全背包求解。

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

答案为将所有符合 $g_k=m$ 的 $f_{n,k}$ 相加。

时间复杂度为 $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;
}