P7961 [NOIP2021] 数列

· · 题解

传送门

\texttt{Description}

题面很友好，略。

\texttt{Data Range:}1\le k\le n\le30,0\le m\le100,1\le v_i<998244353

\texttt{Solution}

看到这种题容易想到 dp。

我们发现，S 的二进制表示位中 1 的数量会涉及进位的问题。由于进位是从低位向高位进行的，所以考虑在 S 中从低位到高位按位 dp（最低位为第 0 位）。

设计 dp 状态 f(i,j,k,p) 表示：讨论了 S 从低到高的前 i 位，已经确定了 j 个序列 a 中的元素，S 从低到高前 i 位中有 k 个 1，要向当前讨论位的下一位进位 p。

因为从上一个状态转移到 f(i,j,k,p) 细节太多，所以考虑用 f(i,j,k,p) 往后转移。

接下来讨论第 i 位（位从 0 开始编号）。假设序列 a 中有 t 个元素为 i，那么就相当于给 S 的第 i 位贡献了 t 个 1，再加上上一位进过来的 p 个 1，总共有 t+p 个 1。

我们知道，当前位每两个 1 可以向下一位进一个 1。所以 (t+p)\bmod2 的结果即为全部进位后当前位是否为 1。同理，向下一位进的 1 的个数即为 \left\lfloor\frac{t+ p}{2}\right\rfloor。

所以 f(i,j,k,p) 往后转移的状态应该是

p}{2}\right\rfloor)

由于乘积之和的形式满足乘法分配律，所以不难想到 f(i,j,k,p) 对新状态的贡献应该是

f(i,j,k,p)\times v_i^t\times\binom{n-j}{t}

初始化 f(0,0,0,0)=1。

如何统计答案呢？对于 i 这一维，由于 a 中元素的范围是 0\sim m，所以 S 只用看总共 m+1 位，所以是 m+1。对于 j 这一维，最终 n 个元素都要确定，所以是 n。对于 k 这一维，应该是在 0\sim k 之间的（后面这个 k 是输入的 k）。p 这一维就随便了。

不过有一个小细节，就是在 S 的第 m 位有可能还要往后面进位，所以可以使用一个 \mathrm{popcnt}(p) 的函数快速统计出进完位后第 m 位往后的 1 的个数，再加上 k 这一维的数量，如果小于等于输入的 k，就可以统计进答案。

注意还要预处理每个 $v$ 的幂次方结果以及组合数，代码过程中的取模问题等。 这道题还可以用滚动数组进行空间优化，~~不过我懒~~。 **时间复杂度：$\mathcal{O}(n^4m)$** ## $\texttt{Code} 
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const ll mod = 998244353;

ll ans, v[105], dp[105][35][35][16], pv[105][35];

ll C[35][35];
inline void init(int n) {
    for (int i = 0; i <= n; i++) C[i][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
}

inline int popcnt(int n) {
    int res = 0;
    while (n) res += n & 1, n >>= 1;
    return res;
}

int main() {
    init(30);
    int n, m, K;
    scanf("%d %d %d", &n, &m, &K);
    for (int i = 0; i <= m; i++) {
        scanf("%lld", &v[i]);
        pv[i][0] = 1;
        for (int j = 1; j <= n; j++) pv[i][j] = pv[i][j - 1] * v[i] % mod;
    }
    dp[0][0][0][0] = 1;
    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 >> 1; p++)
                    for (int t = 0; t <= n - j; t++) dp[i + 1][j + t][k + (t + p & 1)][t + p >> 1] = (dp[i + 1][j + t][k + (t + p & 1)][t + p >> 1] + dp[i][j][k][p] * pv[i][t] % mod * C[n - j][t] % mod) % mod;
    for (int k = 0; k <= K; k++)
        for (int p = 0; p <= n >> 1; p++)
            if (k + popcnt(p) <= K) ans = (ans + dp[m + 1][n][k][p]) % mod;
    printf("%lld", ans);
    return 0;
}