洛谷P7961 [NOIP2021] 数列题解

题目链接：P7961 [NOIP2021] 数列

题意：

给定整数 $n, m,d$，和一个长度为 $m + 1$ 的正整数数组 $v_0, v_1, \ldots, v_m$。

对于一个长度为 $n$，下标从 $1$ 开始且每个元素均不超过 $m$ 的非负整数序列 $\{a_i\}$，我们定义它的权值为 $v_{a_1} \times v_{a_2} \times \cdots \times v_{a_n}$。

当这样的序列 $\{a_i\}$ 满足整数 $S = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_n}$ 的二进制表示中 $1$ 的个数不超过 $d$ 时，我们认为 $\{a_i\}$ 是一个合法序列。

计算所有合法序列 $\{a_i\}$ 的权值和对 $998244353$ 取模的结果。

输入格式：

输入第一行是三个整数 $n, m, d$。

第二行 $m + 1$ 个整数，分别是 $v_0, v_1, \ldots, v_m$。

输出格式：

仅一行一个整数，表示所有合法序列的权值和对 $998244353$ 取模的结果。

数据范围：

对所有测试点保证 $1 \leq d \leq n \leq 30$，$0 \leq m \leq 100$，$1 \leq v_i < 998244353$。

果然是 NOIP 的dp题，这个dp就是很怪。

注意到这个题目最麻烦的就是这个 $S$ 会进位。

进位有什么性质呢，好像除了从低到高进位，没啥特殊的性质。~~但是这已经够dp了~~

设 $f(i,j,k,p)$ 表示讨论了 $S$ 的前 $i~(1\le i \le m+1)$ 位，已经确定了 $j$ 个 $a$ 中的元素，$S$ 从低到高前 $i$ 为中有 $k$ 个 $1$ ，要向当前讨论位（即 $i+1$ ）的进位为 $p$ 时的方案数。边界 $f(0,0,0,0) = 1$ 。

显然考虑刷表法转移。我们枚举序列 $a$ 中有 $t$ 个 $i$ ，则对 $S$ 第 $i$ 位的贡献了 $t$ 个 $1$ 。

而进位还有 $p$ ，所以对 $i+1$ 位的进位为 $\left\lfloor\frac{t+p}{2}\right\rfloor$ ，则转移为

$f\left(i+1,~j+t,~k+(t+p) \bmod 2,~\textstyle\left\lfloor\frac{t+p}{2}\right\rfloor\right) \,\uparrow \,f(i,j,k,p) \times v_i^k \times \binom{n-j}{t}$

最后答案为（其中 $\mathrm{popc}$ 表示种群计数函数 __builtin_popcount() ）

$\sum_{k=0}^{d}\sum_{p=0}^{\left\lfloor\frac{n}{2}\right\rfloor} f(m+1,n,k,p) \times [k + \mathrm{popc}(p) \le d]$

因为 $S$ 有 $m+1$ 位，并且共有 $n$ 个 $a$ ，所以第一位为 $m+1$ ，第二位为 $n$ 。

时间复杂度 $\mathcal{O}(n^4m)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define popc(a) __builtin_popcountll(a)
#define rep(i,a,b) for(int (i)=(a); (i)<=(b); (i)++)
const int mod = 998244353;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x,int y) { (x += y) >= mod ? x -= mod : 0; }
#define mul3(a,b,c) ((a) % mod * (b) % mod * (c) % mod)
#define N ((int)(35))
#define M ((int)(105))

int n,m,d,res,v[M],C[N][N],f[M][N][N][16], pv[M][N];
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;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> d; init(N-5);
    for(int i=0; i<=m; i++)
    {
        cin >> v[i]; pv[i][0] = 1;
        for(int j=1; j<=n; j++)
            pv[i][j] = pv[i][j-1] * v[i] % mod;
    }
    f[0][0][0][0] = 1;
    rep(i,0,m) rep(j,0,n) rep(k,0,d) rep(p,0,n/2) rep(t,0,n-j)
    {
        add(f[i + 1][j + t][k + ((t+p) & 1)][(t+p) / 2],
        mul3(f[i][j][k][p], pv[i][t], C[n-j][t]));
    }
    for(int k=0; k<=d; k++)
        for(int p=0; p<=n/2; p++)
            if(k + popc(p) <= d) add(res, f[m+1][n][k][p]);
    cout << res << '\n';
    return 0;
}