【叫不上名字反正是计数DP】 NOIP2021 T2 数列题解

2020kanade · 2022-07-06 14:12:13 · 题解

人话版题意：给定一个长度为 m 的数列（下标从 0 起），让你选 m个数组成一个权值为所有选取的值的积的序列，这个序列“合法”当且仅当......（参照原题，把 a_i 换成第 i 个选择的数的下标），求所有合法序列的权值和对一个大质数取模的结果。

一般长这样的计数题不是数学就是DP，这道题显然是个DP状物。

什么？数位DP？那是啥！？反正笔者不会，就整了个比较制杖的写法。

以下是一些重要的结论与转化：

关于原题中的约束：把 S 摆成二进制，很容易发现在 S 的组成中，每选一个数，其下标对应的二进制位（从右向左为高，最低为 0 位）上就会 +1。

由第一点，总结出一些特点：数字可以重复选，因此可以枚举某个数字选多少个，而每一个数字和选择该数字的个数（可以为 0 ，代表不选）可以看成一类物品以及这类物品中具体的某一个，符合分组背包的特点。因此，考虑套分组背包的转移，状态下设剩余空间和决策第多少种，转移时枚举某一种选哪一个，对应到这道题上就是当前数字选多少个。

由第二点，我们可以考虑对 S 进行状压来进行二进制相关处理，但最坏情况下 S 会很长，并且其中很大的一部分都不再进行修改了。因此，我们考虑其他的一些状态表示。

每次选数最坏情况下只会影响包括这一位上的二进制的 5 位。

至于为什么......如果对状压熟悉的话，很显然。如果看不出来的话，2^5=32\gt 30 ，之后请自行思考罢。

因此，对于二进制状态的表示，我们可以改成两维：一维代表当前决策的那一个数对应的二进制位置和前面的 4 位（共 5 位）的二进制状压，另一个表示其他信息——注意到这道题关心的是二进制表示中 1 的个数，并且如果是背包的顺序转移，已经决策过的二进制低位不会再发生变化，因此这一维表示当前二进制位置的所有比它低的位中 1 的个数，显然这个数不会超过 n 。

因此，状态出来了：设 dp_{i,j,k,l} 为当前决策的是第 i 个数，剩余空间（还剩多少个位置没选）为 j ， k 与 l 分别是前面说的部分状压和低位 1 的个数时所有序列（不一定合法）的权值和。这里采用发送型转移，因为当前状态的前继难以枚举，但后继状态显然：枚举下一个数字选的个数 s ，则当前状态可以转移到 dp_{i+1,j-s,(k>>1)+s,(k\&1)+l} 。边界为 i\in[0,m-1] (因为是发送型) , j\in[0,n],s\le j （剩余空间不能为负） ,k \in [0,n] ,l \in [0,n] 。

继续考虑转移：选择 s 个当前数，因此要乘上 v_{i+1}^s ，同时注意：我们设的状态是权值和，除了转移不能直接写等号之外，当前元素的所有排列都是等价的，因此要乘以所有排列的数量，这其实是一个组合问题（因为只考虑选没选），选了 s 个的贡献为 C_{j}^s （如果不懂，当前剩余空间为 j ，要丢进去 s 个，相当于从 j 个位置里选 s 个位置，这也是为什么 j 定义为“剩余空间”而不是“已用空间”，如果定义是后者则此处是 C_{j+s}^s ，和上式等价）。

最终得到的总的DP方程就是把上面几个拼起来，计数的时候按照 k 与 l 可以直接推出 popcount(S) （提示：需要实现popcount()），累加合法的即可。

初始状态请自行思考（提示：发送型转移的第一次转移依赖哪些状态）。时间复杂度 \Theta (n^4m) ，注意到DP转移时如果 l 超过了限制其后继状态一定不合法，无需枚举，可以剪枝剪到 \Theta(n^3mk) 。

别忘了取模和 long long ，还有预处理组合数以及快速幂。

Code：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL md=998244353;
const int N=37,M=101;
int n,m,_k;
LL dp[M+2][N][N][N],ct[N][M+2][N][N],C[N<<1][N<<1],v[M+2],ans;
//dp[i+1][j-s][(k>>1)+s][(k&1)+l]+=dp[i][j][k][l]*v[i+1]^s*C[j][s]
inline void init_C(int _n)
{
    C[0][0]=1;
    for(int i=1;i<=_n+1;++i) for(int j=0;j<=i;++j) C[i][j]=((j)?(C[i-1][j]+C[i-1][j-1]+md)%md:1)%md;
}
inline int pc(int __k)
{
    int ans=0;while(__k) {if(__k&1) ++ans;__k>>=1;} return ans;
}
inline LL QP(LL a,LL b)
{
    LL ans=1;
    while(b) {if(b&1) ans=ans*a%md;a=a*a%md,b>>=1;}
    return ans%md;
}
inline LL qread()
{
    LL a=0,f=1;char ch=getchar();
    while(ch<'0' || ch>'9') {if(ch=='-') f*=-1;ch=getchar();}
    while(ch>='0' && ch<='9') {a=a*10+(ch-'0');ch=getchar();}
    return a*f;
}
inline void qwrite(LL x)
{
    LL cnt=0;char w[128];
    if(x<0) x*=-1,putchar('-');
    while(x) {w[cnt++]=(x%10)+'0';x/=10;}
    while(cnt--) putchar(w[cnt]);
}
int main()
{
    n=qread(),m=qread(),_k=qread();
    for(int i=0;i<=m;++i) v[i]=qread();
    init_C(n);
    for(int i=0;i<=n;++i) dp[0][n-i][i][0]=QP(v[0],i)*C[n][i];
    for(int i=0;i<m;++i)for(int j=0;j<=n;++j) for(int k=0;k<=n;++k) for(int l=0;l<=_k;++l)
        for(int s=0;s<=j;++s) dp[i+1][j-s][(k>>1)+s][(k&1)+l]=(dp[i+1][j-s][(k>>1)+s][(k&1)+l]+dp[i][j][k][l]%md*QP(v[i+1],s)%md*C[j][s]%md)%md;
    for(int k=0;k<=n;++k) for(int l=0;l<=_k;++l) if(pc(k)+l<=_k) ans=(ans+dp[m][0][k][l])%md;
    qwrite(ans);if(!ans) putchar(48);
    return 0;
}

【叫不上名字反正是计数DP】 NOIP2021 T2 数列 题解

【叫不上名字反正是计数DP】 NOIP2021 T2 数列题解