dp套dp

思想

复习

先重复一下 $dp$ 的本质：$dp$ 将问题以某种顺序解决，其中记录必需的信息作为当前情况下状态，再考虑状态之间的转移以及如何得到答案所需的状态

从自动机的角度来说：把解决问题的某一步操作的所有所需特征打包为一个节点，将所有节点连成 $DAG$ (通常情况下)，在 $DAG$ 上拓扑的跑就是 $dp$ 的转移

进一步思考

现在有一个可以 $dp$ 的问题形式，给定一个答案，有多少种该问题的数据可以使问题的答案是给定的答案

简而言之就是在 $dp$ 的 $DAG$ 上再跑 $dp$

首先找到 $问题\rightarrow 答案$ 的 $\text{dp}$

考虑到 $dp$ 中最重要的是状态，而状态可以被压缩，将 $内层dp$ 的结果作为 $外层dp$ 的状态

具体来说：设 $内层dp - f_{i,j}$ 表示 $i$ 位置的 $j$ 状态，那么 $外层dp - F_{i,P}$ 表示 $内层dp$ 考虑到了节点 $i$ ，要研究的若干个 $内层dp$ 的结果压缩后为 $P$ 作为 $外层dp$ 的状态，$外层dp$ 的目的就是研究此状态的方案数

具体实现详见例题

例题

bzoj3864 Hero meet devil

给一个 $|S|\leq 15$ 的串和数 $m$ ， $\forall k=0\sim |S|$ ，求有多少串 $T$ 满足 $|T|=m$ 且 $|\text{LCS}(S,T)|=k$

先看 $\text{LCS}$ 的 $dp$ ：

$\text{LCS}_{i,j}= \begin{cases} &\text{LCS}_{i-1,j-1}+1 &\text{ $S_i=T_j$ } \\ &\max\{\text{LCS}_{i-1,j},\text{LCS}_{i,j-1}\} &\text{ $S_i\not =T_j$ } \\ \end{cases}$

为了能压缩，找更多的性质：

$\begin{cases} f_{i,j+1}\geq f_{i,j} \\ f_{i,j+1}\leq f_{i,j}+1 \\ \end{cases} \Rightarrow f_{i,*} 的差分数列是一个 0/1 数列$

状压差分后的数组，细节看代码

#include <bits/stdc++.h>
#define rei register int
using namespace std;

const int N=1e3+100;
const int mod=1e9+7;
char s[N];
int n,m,a[N],t[1<<15][4],f[16],f_j[16];
int dp[2][1<<15],ans[16];//dp_{i,j}:当前枚举到兑奖串第i位(但是滚动了)，且和奖章串的LCS(状压后)为j

inline void fix(int &x){ x>=mod ? x-=mod : 0;}

inline int tran(char c){
    switch(c){
        case 'A': return 0;
        case 'T': return 1;
        case 'G': return 2;
        case 'C': return 3;
    }
}

inline int compress(int f[],int mask=0){//压缩到bitmask
    for(rei i=n;i>=1;--i) mask=(mask<<1) | (f[i]-f[i-1]);
    return mask;//mask 0~n-1位依次表示(差分后的)f[1~n]
}

inline void extract(int mask,int f[]){
    for(rei i=0;i<=n-1;++i) f[i]=0;
    for(rei i=0;i<=n-1;++i) f[i+1]=f[i]+((mask>>i)&1);//状压拆开并把差分数组还原为内层dp的第二维
}

inline void init(){
    rei U=(1<<n)-1;//全集
    memset(f,0,sizeof f); memset(f_j,0,sizeof f_j); memset(t,0,sizeof t);
    for(rei i=0;i<=U;++i){
        extract(i,f);//当前f有 (\log i) 位有效位(然而知道这点并没有什么用
        //设 LCS_{x,y} 表示S前x位，T前y位的LCS长度
        //那么f[]相当于LCS[x-1][],f_j相当于LCS[x][]
        for(rei c=0;c<=3;++c){
            memset(f_j,0,sizeof f_j);
            for(rei j=1;j<=n;++j){//内层做lcs的dp，f_j相当于正常dp时f的第二维
                f_j[j]=max(f[j],f_j[j-1]);
                if(c==a[j]) f_j[j]=max(f_j[j],f[j-1]+1);
            }
            t[i][c]=compress(f_j);//t[i][c]:字符串i加上字符c后与串S的(状压后的)LCS
        }
    }
}

signed main(){
    rei T; scanf("%d",&T);
    while(T--){
        scanf("%s%d",s+1,&m); n=strlen(s+1);
        for(rei i=1;i<=n;++i) a[i]=tran(s[i]);
        init();
        rei U=(1<<n)-1; memset(dp,0,sizeof dp); memset(ans,0,sizeof ans);
        rei pre=0,cur=1; dp[pre][0]=1;
        for(rei i=1;i<=m;++i){//每循环一次会比上次多一个字符
            for(rei j=0;j<=U;++j) for(rei c=0;c<=3;++c) fix(dp[cur][ t[j][c] ]+=dp[pre][j]);//由t的定义显然
            pre^=1,cur^=1; memset(dp[cur],0,sizeof dp[cur]);
        }
        for(rei i=0;i<=U;++i) fix(ans[ __builtin_popcount(i) ]+=dp[pre][i]);
        for(rei i=0;i<=n;++i) printf("%d\n",ans[i]);
    }
    getchar(),getchar();
    return 0;
}

P4590 [TJOI2018]游园会

给定字符串 $s$ ，数 $n$ ，$\forall i\in[0,|S|]$ 求有多少字符串 $t$ 满足 $|t|=n$ 且 $s$ 与 $t$ 的最长公共子序列长度 $i$ ，其中 $s,t$ 均由 N O I 三个字母组成，且 $t$ 中不能含有子串 NOI

与上题类似，$f$ 多开一维记录是否有后缀 N NO 以避免 NOI 出现

const int K=30;
const int N=1e3+100,S=1<<15;
const int mod=1e9+7;
char s[N];
int n,k;
int f[2][S][3],ans[N];
int g[K],h[K],Size[S];

inline void fix(int &x){ x>=mod ? x-=mod : 0;}

inline int compress(int mask=0){//压缩到bitmask
    for(rei i=1;i<=k;++i) mask|=(h[i]-h[i-1])<<(i-1);
    return mask;//mask 0~n-1位依次表示f[1~n]
}

inline void extract(int mask){
    for(rei i=1;i<=k;++i) g[i]=mask>>(i-1)&1;
    for(rei i=1;i<=k;++i) g[i]+=g[i-1];
}

inline void trans(int a,int b,char c,int st,int v){
    extract(st);
    for(rei i=1;i<=k;++i){
        h[i]=max(g[i],h[i-1]);
        if(c==s[i]) h[i]=max(h[i],g[i-1]+1);
    }
    rei now=compress();
    fix(f[a][now][b]+=v);
}

int main(){
    scanf("%d%d",&n,&k); scanf("%s",s+1);
    rei U=1<<k;
    f[0][0][0]=1;
    for(rei i=0;i<n;++i){
        rei p=i&1,q=p^1;
        memset(f[q],0,sizeof f[q]);
        for(rei j=0;j<U;++j){
            rei *t=f[p][j];
            if(t[0]){
                trans(q,1,'N',j,t[0]);
                trans(q,0,'O',j,t[0]);
                trans(q,0,'I',j,t[0]);
            }
            if(t[1]){
                trans(q,1,'N',j,t[1]);
                trans(q,2,'O',j,t[1]);
                trans(q,0,'I',j,t[1]);
            }
            if(t[2]){
                trans(q,1,'N',j,t[2]);
                trans(q,0,'O',j,t[2]);
            }
        }
    }
    for(rei i=0;i<U;++i) Size[i]=Size[i>>1]+(i&1);
    for(rei i=0;i<U;++i) for(rei j=0;j<3;++j) fix(ans[ Size[i] ]+=f[n&1][i][j]);
    for(rei i=0;i<=k;++i) printf("%d\n",ans[i]);
    getchar(),getchar();
    return 0;
}

P4484 [BJWC2018]最长上升子序列

长度为 $n$ 的随机排列，求其最长上升子序列长度的期望

仍是先考虑 $内层dp \ \text{LIS}$ 的 $O(n\log n)$ 做法：$dp$ 数组记录每个长度的上升子序列的最后一项的最小值

具体操作是：

构造 $n+1$ 个序列 $L_0\sim L_n$ ，其中序列 $L_{i,j}$ 表示原数组 $A$ 的前 $i$ 个中，能构成的所有长度 $j$ 的 $\text{LIS}$ 中，结尾最小的序列的结尾数字
- 设 $L_0=\varnothing$
- 若 $L_{i-1}$ 已经被求出且 $A_i$ 大于 $L_{i-1}$ 中每个元素，直接将 $A_i$ 接在 $L_{i-1}$ 后面形成 $L_i$
- 若 $L_{i-1}$ 中存在最小的比 $A_i$ 大的元素 $x$ ，那么用 $A_i$ 替换掉 $x$ 以形成 $L_i$
由此，$L_n$ 的长度就是 $A$ 的 $\text{LIS}$ 长度

可以发现，对于任意一个排列的前缀，只需要存这个数组而不是整个排列就能得到全部所需信息

由于原数组是一个排列，该数组中不含相同元素，故数组中前 $i$ 个数对应的 $dp$ 数组只有不超过 $2^i$ 中可能

设 $f_{i,S}$ 表示长度为 $i$ 的排列的 $\text{LIS} \ dp$ 数组为 $S$ 的概率

转移时枚举长度 $i+1$ 的排列的最后一个元素 $k$ ，将 $S$ 中所有 $\geq k$ 的数 $+1$ ，更新 $dp$ 数组

UOJ#141. 【UER #4】量子态的棋盘

~~无法简述的题干~~

小球数 $K\leq 10^{18}$ ，但注意到若落在某个网格内的小球为偶数个，则一半往下一半往右，仅当小球个数奇数时，最后一个小球的走向与格子权值有关

先推一遍 $dp$ ，留下不确定走向的小球，如此最多有 $n\times m$ 个球

~~由官方题解得~~一个点的状态数 $S\leq 5\times 10^5$

对轮廓线状压，复杂度为 $O(nmS+Q)$

把轮廓线上的球数转化为 $80$ 进制数并和当前已经入袋的球数 $hash$，存到 $hashmap$ 里

写不出来放弃了哈哈哈

LOJ#6274数字

求 $\text{card}(\{x\and y|x\or y=T,x\in [L_x,R_x],y\in [L_y,R_y]\})$ ，其中所有数 $\leq 2^{60}$

考虑如何验证 $x\and y=V$ : 数位 $dp$ ：设 $f_{i,a,b,c,d}$ 表示第 $i$ 位上 $x,y$ 与 $\{L_x,R_x\},\{L_y,R_y\}$ 的关系(即是否顶到上下界)

将这 $16$ 个数( $xy\in\{0,1\}$, $4$ 种取值，每种取值对应 $a,b,c,d$ $4$ 个数)压起来，$dp_{i,S}$ 表示第 $i$ 位，$f$ 的 $16$ 个值 $S$ 情况下有多少满足条件的 $V$

inline int sta(int a,int b,int c,int d){return a | b<<1 | c<<2 | d<<3;}

int main(){
    ...
    dp[60][1<<sta(1,1,1,1)]=1;
    for(rei i=59;~i;-- i){
        rei t=T>>i&1,lx=Lx>>i&1,rx=Rx>>i&1,ly=Ly>>i&1,ry=Ry>>i&1;
        for(rei S=0;S<65536;++S) if(dp[i+1][S])
            for(rei v=0;v<2;++v){
                rei Next=0;
                for(rei SS=0;SS<16;++SS) if(S>>SS&1){
                    rei a=SS&1,b=SS>>1&1,c=SS>>2&1,d=SS>>3&1;
                    for(rei x=0;x<2;++x) for(rei y=0;y<2;++y)
                        if((x|y)==t && (x&y)==v && (!a || x>=lx) && (!b || x<=rx) && (!c || y>=ly) && (!d || y<=ry))
                            Next|=1<<sta(a && x==lx,b && x==rx,c && y==ly,d && y==ry);
                }
                dp[i][Next]+=dp[i+1][S];
            }
    }
    for(rei S=1;S<65536;++S) ans+=dp[0][S];
    ...
}

P5279 [ZJOI2019]麻将

$n$ 种不同的牌，大小 $1\sim n$ ，每种牌都有 $4$ 张。

定义面子为形如 $\{i,i,i\} (1\leq i\leq n) 或 \{i,i+1,i+2\}(1\leq i\leq n-2)$ 的三张牌(这个样子叫做刻子)；对子为形如 $\{i,i\}(1\leq i\leq n)$ 的两张牌

定义麻将牌集合 $S$ 是胡的当且仅当其大小为 $14$ 且满足至少一个下列条件：$1.$ $S$ 可以被划分成 $5$ 个集合 $S_1\sim S_5$ ，其中 $S_1$ 是对子， $S_{2\sim 5}$ 是面子；$2.$ $S$ 可以被划分成 $7$ 个集合 $S_1\sim S_7$ ，它们都是对子，且对应的大小两两不同

先摸出 $13$ 张牌，并等概率随机打乱剩下的 $4n-13$ 张，对于排列 $P$ ，$S_i$ 为摸出的 $13$ 张加上 $P$ 中前 $i$ 张牌的集合，设 $P$ 权值为最小的 $i$ 满足 $S_i$ 存在一个子集是胡的，求 $P$ 的权值的期望

~~只会打 $20$ 暴力啊啊啊wtcl~~

内层

先考虑简化题中条件，不难把牌简化成一个长度 $n$ 的字符串，即，第 $i$ 位表示第 $i$ 种牌出现的次数

考虑如何会胡牌：

$7$ 个对子：显然判断一下奇偶就可以，不作讨论
选 $1$ 种牌当对子，剩下的求出最大的面子数量 $\geq 4$

考虑第二种情况：不难得出 $f_{0/1,i,j,k}$ 表示有无对子，第 $i-1$ 种牌开头的顺子有 $j$ 个，第 $i$ 种牌开头的顺子有 $k$ 个且其余牌全部是刻子(三个牌都一样)的最大面子数

那么要通过加牌使这个 $dp$ 最终的状态是胡的

开一个结构体 $PAI={\text{data}f_{0/1,j,k},DZ}$ 记录 $dp$ 状态及对子数，每当 $f_{1,0,0}\geq 4 \lor DZ\geq 7$ 时，胡牌

设 $trans(f,x)$ 表示在 $dp$ 状态 $f$ 后加一种新的牌 $x$ 张得到的状态，$\max(f,g)$ 表示 $f,g$ 两个状态种取最优所得的状态，那么有转移：

$\begin{cases} f_0=trans(f_0',x) \\ f_1=\max(trans(f_1',x),[x\geq 2] \ trans(f_0',x-2)) \\ DZ=DZ'+[x\geq 2] \\ \end{cases}$

考虑到胡牌的情况，将 $f$ 中所有值与 $4$ 取 $\min$ ,$DZ$ 与 $7$ 取 $\min$ ，$dfs$ 发现不同的状态只有 $m=3956$ 个，同时预处理 $son_{s,k}$ 表示 $\text{PAI} \ s$ 在后面加上 $k$ 达到的 $\text{PAI}$

外层

要求最早胡牌巡目数 $i$ ，转化为求巡目数为 $i$ 但仍不是胡的概率 $p_i$ ，由期望公式得：

$E(x)=\sum_{i=14}^{4n-13}P(x=i)=\sum_{i=13}^{4n-14}P(x>i)=\sum_{i=13}^{4n-14}p_i$

设 $f_{i,j,s}$ 表示前 $i$ 种牌选 $j$ 张后到了 $\text{PAI} s$ 的方案数，每次枚举第 $i$ 种牌选了 $k$ 张，有转移：

$f_{i,j+k,son_{s,k}}=\binom{j+k-sum_i}{k-a_i}A_{4-a_i}^{k-a_i} \times f_{i-1,j,s}$

其中 $a_i$ 表示第 $i$ 种牌刚开始时摸到的张数，$sum_i=\sum_{j=1}^i a_j$ ，及从 $4-a_i$ 张牌种选出 $k-a_i$ 张进行排列并插入到之前的 $j$ 张牌中，但有 $sum_i$ 张牌默认在最前面，

最后有

$p_i=\frac{\sum_{s=1}^m f_{n,i,s}}{A_{4n-13}^{i-13}}$

const int N=100,M=3956,NN=(N<<2)+5;
const int mod=998244353;

inline void fix(int &x){ x>=mod ? x-=mod : 0;}
inline void fix(ll &x){ x>=mod ? x-=mod : 0;}
inline int qpow(int w,int b){int s;for(s=1;b;b>>=1,w=(ll) w*w%mod) if(b&1) s=(ll) s*w%mod; return s;}

struct Data{
    int f[3][3];//f_{j,k}
    inline Data(){ for(rei i=0;i<3;++i) for(rei j=0;j<3;++j) f[i][j]=-1;}
    inline bool operator <(const Data &a)const{
        for(rei i=0;i<3;++i) for(rei j=0;j<3;++j) if(f[i][j]!=a.f[i][j]) return f[i][j]<a.f[i][j];
        return false;
    }
    inline Data operator *(int x){//*重新定义为添加：x为一种新牌的数量
        Data c; c=Data();
        for(rei i=0;i<3;++i) for(rei j=0,F;j<3;++j)
            if(~(F=f[i][j])) for(rei k=0;k<3 && i+j+k<=x;++k) c.f[j][k]=max(c.f[j][k],F+i+(x-i-j-k)/3);//添加的x是否能成为刻子
        for(rei i=0;i<3;++i) for(rei j=0;j<3;++j) c.f[i][j]=min(c.f[i][j],4);
        return c;
    }
    inline void Fix(Data c){
        for(rei i=0;i<3;++i) for(rei j=0;j<3;++j) f[i][j]=max(f[i][j],c.f[i][j]);
    }
};

struct PAI{
    Data f[2];/*f_{0/1,j,k}*/int DZ;
    inline PAI(){f[0].f[0][0]=DZ=0;}
    inline bool operator <(const PAI &a) const{return mk(mk(f[0],f[1]),DZ)<mk(mk(a.f[0],a.f[1]),a.DZ);}
    inline PAI operator *(int x){
        PAI c;
        c.f[0]=f[0]*x;c.f[1]=f[1]*x;c.DZ=DZ;
        if(x>=2) c.f[1].Fix(f[0]*(x-2)),c.DZ=min(DZ+1,7);//查看7对子的情况
        return c;
    }
    inline bool HU(){ return DZ>=7 || f[1].f[0][0]>=4;}
};

int n,a[N+5];
int m,son[M+5][5];
bool HU[M+5];
map<PAI,int> S;
int C[NN][NN],fac[NN],f[2][NN][M+5],ans;

inline void init(int n){
    for(rei i=C[0][0]=1;i<=n;++i) for(rei j=C[i][0]=1;j<=i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
    fac[0]=1;
    for(rei i=1;i<=n;++i) fac[i]=(ll) fac[i-1]*i%mod;
}

int dfs(PAI x,int st=1){
    if(S.count(x)) return S[x];
    rei ID=(S[x]=++m); HU[ID]=x.HU();
    for(rei i=0;i<=4;++i) son[ID][i]=dfs(x*i,st+1);
    return ID;
}

int main(){
    scanf("%d",&n);
    dfs(PAI());
    for(rei i=1,x,y;i<=13;++i) scanf("%d%d",&x,&y),++a[x];
    init(n<<2); f[0][0][1]=1;
    for(rei i=1,c=1,sum=0;i<=n;++i,c^=1){
        for(rei j=0;j<=(i<<2);++j) for(rei k=1;k<=m;++k) f[c][j][k]=0;
        sum+=a[i];
        for(rei j=0;j<=(i-1<<2);++j) for(rei s=1,G;s<=m;++s){
            G=f[c^1][j][s]; if(!G) continue;
            for(rei k=a[i];k<=4;++k){
                if(HU[ son[s][k] ]) continue;
                rei &F=f[c][j+k][ son[s][k] ];
                fix(F+=(ll) G*C[j+k-sum][ k-a[i] ]%mod*C[ 4-a[i] ][ k-a[i] ]%mod*fac[ k-a[i] ]%mod);
            }
        }
    }
    for(rei i=13;i<(n<<2);++i){
        rei sum=0;
        for(rei s=1;s<=m;++s) fix(sum+=f[n&1][i][s]);
        fix(ans+=(ll) sum*qpow((ll) C[ (n<<2)-13 ][i-13]*fac[i-13]%mod,mod-2)%mod);
    }
    printf("%d\n",ans);
    getchar(),getchar();
    return 0;
}