谈一类计数dp——dp套dp

一、dp套dp的定义

dp套dp就是一种将dp的值存入另一个dp的状态，而外层另作一个dp去取得记录这种状态的方案数。

二、dp套dp的搜索表征

对于一般的计数dp而言，其搜索形如：

void DFS(int x){
    if(x==n+1)return void(ans+=Check());
    for(int i=1;i<=m;i++){
        ...
        DFS(x+1)
        ...
    }
}

如果这个Check()是一个朴素的对决策的检查，那么转换后是一个朴素计数dp，往往去维护一些 Check() 里面关心的量，但如果 Check() 需要一个 dp 去实现，那么转换后就是一个dp套dp。

三、dp套dp 的实现，内层应该存储什么？

很简单，内层应该存储可以等价实现 Check() 转移的信息。
我们搜索的内容就是我们的决策，那么就应该存储最少的信息与决策相结合是可以进行Check() 函数中的转移。

但如果内层dp不是一个Check()而是另一个计数dp，那么不是传统的dp套dp，即外层状态不能是内层状态的值，而是因该将内层状态与外层状态合并，使得可以通过外层决策转移，见2024.11.22T3 Transformation.

四、例题

首先不难写出一个搜索：

void Deal(){
    for(int i=1;i<=n;i++){
        f[i]=1;
        for(int j=1;j<i;j++)if(mp[j][i]&&(c[i]^c[j]))f[i]^=f[j];
    }
    int res=0;
    for(int i=1;i<=n;i++)res^=f[i];
    ans+=(res==p);
    return;
}
void DFS2(int x,int y){
    if(y==n+1)return DFS2(x+1,x+2);
    if(x==n+1)return Deal();
    mp[x][y]=1;
    DFS2(x,y+1);
    mp[x][y]=0;
    DFS2(x,y+1);
    return;
}
void DFS1(int x){
    if(x==n+1)return DFS2(1,2);
    if(c[x]!=-1)return DFS1(x+1);
    c[x]=0;
    DFS1(x+1);
    c[x]=1;
    DFS1(x+1);
    c[x]=-1;
    return;
}

我们发现这个搜索的Check是以一个dp实现的（即Deal()函数），那么我们考虑用dp套dp优化，首先发现这个Deal()的决策是什么，显然就是我们所搜的mp与c。

我们假设在位置 \(i\) 的时候仅仅决策 \(c_i\) 与 \(\forall j<i,mp[j][i]\)，发现 \(f_i\) 的值，仅与 \(f_j=1\land c_j\ne c_i\) 的 \(j\) 有关，并且这些 \(j\) 是无标号的，你可以在这些 \(j\) 中选取偶数个连边使得 \(f_i=1\)，或者选取奇数个连边使得 \(f_i=0\)，其他的随便连边，不会影响 \(f_i\) 的值所以你可以这样设计外层dp的状态：

设 \(dp_{i,x,y}\) 表示考虑 \(1\sim i\) 的节点，\(\sum_{j<i\land c_j=0}[f_j=1]=x,\sum_{j<i\land c_j=1}[f_j=1]=y\) 时的连边方案数，考虑一次 \(i\to i+1\) 的扩展。

• 当 \(c_i=0\)：

  • 选择奇数条边，那么 \(x\to x+1\)，所以：\(dp_{i+1,x+1,y}\leftarrow dp_{i,x,y}\times (\sum_{i=0}^{\lfloor\frac y2\rfloor}{y\choose 2i+1})\times 2^{i-y}\)

  • 选择偶数条边，那么 \(x\) 不变，所以：\(dp_{i+1,x,y}\leftarrow dp_{i,x,y}\times \sum_{i=0}^{\lfloor\frac y2\rfloor}{y\choose 2i}\times 2^{i-y}\)

• 当 \(c_i=1\):

  • 选择奇数条边，那么 \(y\to y+1\)，所以：\(dp_{i+1,x,y+1}\leftarrow dp_{i,x,y}\times \sum_{i=0}^{\lfloor\frac x2\rfloor}{x\choose 2i+1}\times 2^{i-x}\)

  • 选择偶数条边，那么 \(y\) 不变，所以：\(dp_{i+1,x,y}\leftarrow dp_{i,x,y}\times \sum_{i=0}^{\lfloor\frac x2\rfloor}{x\choose 2i}\times 2^{i-x}\)

因为有公式 \(\sum_{i=0}^{\lfloor\frac y2\rfloor}{y\choose 2i+1}=[y>0]2^{y-1},\sum_{i=0}^{\lfloor\frac y2\rfloor}{y\choose 2i}=[y>0]2^{y-1}+[y=0]2\)

所以原转移可以化简为一个不与 \(x,y\) 具体的值有关，但与 \(x,y\) 是否大于 \(0\) 有关。

于是令 \(dp_{i,x',y'}\) 中表示 \(x',y'\) 分别表示 \(x,y\) 是否大于 \(0\)，由于最后统计答案还要看 \(x+y\) 的奇偶性，所以再开一维 \(j\) 表示就行了，复杂度 \(\mathcal O(n)\)。