P7961 [NOIP2021] 数列

题目描述

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

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

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

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

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

5 1 1
2 1

输出 #1

40

输入输出样例 #2

输入 #2

8 9 4
934258593 150407625 187068439 162292791 219945760
512449588 803393963 983648121 484675481 412407699

输出 #2

642171527

说明/提示

【样例解释 #1】

由于 $k=1$，而且由 $n\le S\le n\times 2^m$ 知道 $5\le S\le 10$，合法的 $S$ 只有一种可能：$S=8$，这要求 $a$ 中必须有 $2$ 个 $0$ 和 $3$ 个 $1$，于是有 $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$ 种可能的序列，每种序列的贡献都是 $v_0^2{v}_1^3=4$，权值和为 $10\times 4=40$。

【数据范围】

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

测试点	$n$	$k$	$m$
$1\sim 4$	$=8$	$\le n$	$=9$
$5\sim 7$	$=30$	^	$=7$
$8\sim 10$	^	^	$=12$
$11\sim 13$	^	$=1$	$=100$
$14\sim 15$	$=5$	$\le n$	$=50$
$16$	$=15$	^	$=100$
$17\sim 18$	$=30$	^	$=30$
$19\sim 20$	^	^	$=100$

首先看到数据范围，$n=30$，$m=100$，非常小，但如果你觉得这道题很简单，那就完蛋了，首先你必须想到，这是NOIP的T2，CCF肯定不会出一道简单题，那么你就要小心了，因为这很可能是一道高维动态规划（事实也确实如此）。

首先，如果你对于这道题目无从下手，教你一个技巧：先考虑去掉几个限制条件。你认为最难做的约束是什么？显然是$S$在二进制下不超过$k$个$1$。那我们把这个限制去掉会发生什么？那就是说，在$0$到$m$中，有序地选择$n$个，组成数列{an}\{a_n\}{an​}，计算所有${\prod }_{i=1}^n{v}_{a_i}$,那么很明显，这就是一道完全背包问题！状态转移方程很明显，就是：
$$dp[i][j]=\sum _{u=0}^j\left(\genfrac{}{}{0ex}{}{j}{u}\right)v_i^u\cdot dp[i-1][j-u]$$
其中$u$表示选取了$u$个$i$，而答案就是$dp[n][m]$。

现在我们再考虑$S$在二进制下不超过$k$个$1$。由于在上述完全背包中，每次选取的个数是枚举出来的，也就是说是确定的（即为$p$个），那么$S^{\prime }$就等于$S+p\cdot 2^i$，于是状态转移方程：
$$dp[i][j][p+u\cdot 2^i]=\sum _{u=0}^j\sum _{p=0}^{(j-u)\cdot 2^{i-1}}\left(\genfrac{}{}{0ex}{}{j}{u}\right)v_i^u\cdot dp[i-1][j-u][p]$$
提前处理每个数在二进制下有几个$1$，设这个数组为$g[u]$，答案就是
$$\sum _{p=n}^{n\cdot 2^m}dp[m][n][p]\cdot (g[p]<=k)$$
显然，由于最大$m=100$，数组不可能开这么大，就算能开这么大也不可能在限制时间内跑完（时间复杂度$O(m\cdot n^2\cdot 2^m)$）。我们需要一个优化算法。

再说一个实用的小技巧：根据数据范围确定维度数量。观察到$n=30$，$m=100$，由此可以肯定动态规划至少是$4$维的。

怎么进行优化呢？让我们想一想：原来的枚举每个$S$复杂度太高，但每个$S$在二进制下每一位都是需要储存的有效信息吗？显然不是，我们发现：由于我们按照从$0$到$m$的顺序进行枚举，那么对于$S$的影响，必定是以$2^i$为单位的，也就是说，第$i$位以下有多少个$1$，每个$1$分别在哪个位置都对后续规划无影响！

那么，我们就已经优化掉$2^{i-1}$位了，再思考一下：对于每一位，我们最多只能选$n$个，也就是说，$S$变化量最多只有$n\cdot 2^i$，而我们已经优化掉了$2^{i-1}$位，也就是说，$S$已经右移了$i-1$位，那么$S$的变化量最多就只有$n$了！但我们依然要储存二进制当前有多少个$1$，于是还要多开一个维度，表示二进制当前有多少个$1$。

好了，现在我们有四个维度，设为$i$、$j$、$p$、$q$，表示正在选第$i$位，选完之后总共选了$j$个数，$S$的二进制在第$i$位及其高位的数为$p$（这样讲比较抽象，实际就是$S$右移$i-1$位所得的数是$p$），这个序列的$S$值中有$q$个$1$，现在我们依次考虑这几个数怎么更新。

显而易见地，对于第一维，用$i-1$去更新$i$，对于第二维，用$j-u$去更新$j$。

剩下两维是重点考虑对象。对于第三维，由于我们只考虑$S$二进制下$i$位及以上，考虑第$i-1$维时的$p$值，由于我们需要更新到第$i$位，所以$p$需要右移一位，然后我们又选了$u$个$i$，因此还要加上$u$，也就是说，用$u$去跟新$u+p/2$。

最后一维是$S$在二进制下$1$的个数。由于低于$i$位不会受影响，只需要考虑$i$位及以上的$1$的个数变化，原来从第$i$位开始的数是$p/2$，现在第$i$位开始的数是$u+p/2$，用到之前我们所求的$g$数组，$1$的个数变化量就是$g[u+p/2]-g[p/2]$，也就是说，用$v$去更新$v+g[u+p/2]-g[p/2]$。

那么状态转移方程就显而易见了：
$$dp[i][j][u+p/2][v+g[u+p/2]-g[p/2]]=\sum _{u=0}^n\sum _{p=0}^n\sum _{q=0}^n\left(\genfrac{}{}{0ex}{}{j}{u}\right)v_i^u\cdot dp[i-1][j-u][p][q]$$
由于用$i-1$去更新$i$，所以要初始化$i=0$时，这很简单，由于$j=u$、$p=0$、$q=0$，所以原方程可简化为：
$$dp[0][u][u][g[u]]=v_0^u$$
最终输出的答案就是：
$$\sum _{p=0}^n\sum _{q=0}^{k}dp[i][j][p][q]$$
最后几个细节：预处理$v_i$的幂次和组合数，不然会TLE；对于$dp[i-1][j-u][p][q]=0$直接跳过，不跳也会TLE；时时刻刻取模，保险一点开$long$ $long$；在状态转移过程中枚举$q$的时候范围千万不要写成$0$到$k$，否则只有$30$分，因为中间过程$S$的$1$的个数超过$k$不代表最终结果也超过$k$。

AC代码~~（时间复杂度$O(n^{4}m)$）：

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int g[105];//每一个数二进制下有几个1
long long v[105];
long long f[105][35][35][35];//动态规划数组
long long co[35][35];//组合数
long long MOD=998244353;//取模
long long po[105][35];//v的幂次
long long ans;//最终答案
int cal(int t){//计算每一个数二进制下有几个1
    int s=0;
    while(t){
        s+=(t&1);
        t>>=1;
    }
    return s;
}
int main(){
    cin>>n>>m>>k;
    for(int i=0;i<=m;i++){
        cin>>v[i];
    }
    for(int i=0;i<100;i++){//预处理g数组
        g[i]=cal(i);
    }
    for(int i=0;i<=n;i++){//初始化组合数
        co[i][0]=1;
        co[i][i]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<i;j++){
            co[i][j]=(co[i-1][j]+co[i-1][j-1])%MOD;//计算组合数
        }
    }
    for(int i=0;i<=m;i++){
        po[i][0]=1;
        for(int j=1;j<=n;j++){
            po[i][j]=(po[i][j-1]*v[i])%MOD;//计算v的幂次
        }
    }
    for(int u=0;u<=n;u++){
        f[0][u][u][g[u]]=po[0][u];//初始化动态规划数组
    }
    for(int i=1;i<=m;i++){//枚举第i个数
        for(int j=0;j<=n;j++){//枚举总共选了j个数
            for(int u=0;u<=j;u++){//枚举当前选了u个数
                for(int p=0;p<=n;p++){//枚举S值右移i-1位的结果
                    for(int q=0;q<=n;q++){//枚举S中有q个1
                        if(f[i-1][j-u][p][q]==0){//没有值就跳过
                            continue;
                        }
                        f[i][j][u+p/2][q+g[u+p/2]-g[p/2]]=
                        (f[i][j][u+p/2][q+g[u+p/2]-g[p/2]]+
                        f[i-1][j-u][p][q]*po[i][u]%MOD*co[j][u]%MOD)%MOD;
                        //状态转移
                    }
                }
            }
        }
    }
    for(int p=0;p<=n;p++){
        for(int q=0;q<=k;q++){
            ans=(ans+f[m][n][p][q])%MOD;//累加结果
        }
    }
    cout<<ans;//输出
    return 0;
}