洛谷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;
}