luoguP7961 [NOIP2021] 数列

dp，个人认为难点在组合数

数列

思路

考虑 dp ， $n, m$ 比较小，于是大力叠状态，估计一下大概是个 $O(n^4m)$ ，盲猜 $O(n)$ 转移，所以状态大概是 $O(n^3 m)$ 即四维的

关键在于统计 $1$ 的个数，直接记录 $S$ 为状态不可能，把 $m++$ ，定义 $d[i, j, k, p]$ 为“在 $v_1 \sim v_i$ 中选了 $j$ 个数，现在有 $k$ 个 $1$ ，还要往前进位 $p$ 个 $1$ 的权值和”，转移就枚举当前数选的个数 $q$ ：
$$
d[i, j, k, p] \times v_{i + 1}^{q} \to d[i + 1, j + q, k + ((p + q) \& 1), (p + q) >> 1]
$$
打完，发现 WA ，原因是 $a_i$ 是有序的，所以答案还要乘一个排列数；这里我就伞兵了，竟然又开了一个 dp 数组 $g$ 来计算排列，其实，只需再乘一个 $\binom{n - j}{q}$ 即可，就是“从 $n - j$ 个空的数中选 $q$ 个”

代码

#include <bits/stdc++.h>
#define FF std::function
using LL = long long;
const int N = 30 + 10, M = 100 + 10, P = 998244353;
int n, m, K, v[M], f[M][N][N][N], ans, fac[N], ifac[N];
int main()
{
    scanf("%d %d %d", &n, &m, &K), ++m;
    for (int i = 1; i <= m; ++i) scanf("%d", &v[i]);
    f[0][0][0][0] = fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
    FF<void(int&, int)> add = [&](int &x, int y){ if ((x += y) >= P) x -= P; };
    FF<int(int, int)> qpow = [&](int x, int y)
    {
        int res = 1;
        for (; y; y >>= 1, x = LL(x) * x % P) if (y & 1) res = LL(res) * x % P;
        return res;
    }, 
    C = [&](int x, int y){ return LL(fac[x]) * ifac[y] % P * ifac[x - y] % P; } ;
    for (int i = 2; i <= n; ++i) fac[i] = LL(fac[i - 1]) * i % P;
    ifac[n] = qpow(fac[n], P - 2);
    for (int i = n - 1; i >= 2; --i) ifac[i] = LL(i + 1) * ifac[i + 1] % P;
    for (int i = 0; i <= m; ++i)
        for (int j = 0; j <= n; ++j)
            for (int k = 0; k <= K; ++k)
                for (int p = 0; p <= n; ++p) if (f[i][j][k][p])
                    for (int q = 0; q + j <= n; ++q)
                        add(f[i + 1][j + q][k + ((p + q) & 1)][(p + q) >> 1], LL(f[i][j][k][p]) * C(n - j, q) % P * qpow(v[i + 1], q) % P);
    for (int k = 0; k <= K; ++k)
        for (int p = 0; p <= n; ++p) if (f[m][n][k][p])
        {
            int ct = 0, t = p;
            while (t) ct += t & 1, t >>= 1;
            if (ct + k <= K) add(ans, LL(f[m][n][k][p]));
        }
    printf("%d\n", ans);
    return 0;
}