题解 P7142 【[THUPC2021 初赛]密集子图】

· · 题解

考虑最短路树，对于深度为 i 的某个点，深度小于 i-1 的点不能向其连边，至少有一个深度为 i-1 的点向其连边，对于其他点连向它的边没有限制。

这启发我们分层状压 dp。设 f_{d,s_1,s_2} 为，深度为 d 的点的集合为 s_1，深度小于等于 d 的点的集合为 s_2，只考虑连向深度大于 d 的点的边的限制，时，图满足条件的概率。

考虑转移。枚举深度为 d+1 的点的集合 s_3，则 s_1-s_2 内的点都不能向 s_3 内的点连边，且对于 s_3 内的每一个点，s_2 内至少有一个点需要向其连边。dp 值即为每个这样的 s_3 符合条件的概率之和。

直接实现即可做到 O(\operatorname{poly}(n)4^n) 的复杂度，因为这个 dp 实际上相当于枚举子集的子集。

对于每个 s_1 和 s_2，预处理 s_1 内的点都不向 s_2 内的点连边的概率，和对于每个 s_2 内的点 s_1 内的点至少有一个向其连边的概率。这部分可以在 O(3^n) 至 O(n4^n) 不等的时间内完成。预处理后每次转移的复杂度降为 O(1)，总时间复杂度为 O(n4^n)。

需要进行一些卡常卡空间。

下面是我的最终代码，使用了滚动数组进行优化，空间 O(4^n)。理论上最好可以做到 O(3^n) 空间。

#include<bits/stdc++.h>
using namespace std;
inline int readint(){
    int x=0;
    bool f=0;
    char c=getchar();
    while(!isdigit(c)&&c!='-') c=getchar();
    if(c=='-'){
        f=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f?-x:x;
}
const int maxn=12;
int n,k;
const int mod=998244353;
int ksm(int a,int b){
    int ans=1;
    while(b){
        if(b%2==1) ans=1ll*ans*a%mod;
        a=1ll*a*a%mod;
        b/=2;
    }
    return ans;
}
inline void mul(int& x,int y){
    x=1ll*x*y%mod;
}
int p[maxn+5][maxn+5];
int f[2][(1<<maxn)+5][(1<<maxn)+5];
int g[(1<<maxn)+5][(1<<maxn)+5],h[(1<<maxn)+5][(1<<maxn)+5];
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    n=readint();
    k=readint();
    for(int i=0;i<n*(n-1);i++){
        int x,y;
        x=readint()-1;
        y=readint()-1;
        p[x][y]=readint();
        mul(p[x][y],ksm(readint(),mod-2));
    }
    int all=(1<<n)-1;
    for(int s1=0;s1<=all;s1++){
        for(int i=0;i<n;i++) if(!(s1>>i&1)){
            g[s1][1<<i]=1;
            for(int j=0;j<n;j++) if(s1>>j&1) mul(g[s1][1<<i],(1-p[j][i]+mod)%mod);
        }
        for(int s2=all^s1;s2;s2=(s2-1)&(all^s1)) if((s2&-s2)!=s2){
            g[s1][s2]=1;
            for(int i=0;i<n;i++) if(s2>>i&1) mul(g[s1][s2],g[s1][1<<i]);
        }
    }
    for(int s1=0;s1<=all;s1++){
        for(int i=0;i<n;i++) if(!(s1>>i&1)) h[s1][1<<i]=(1-g[s1][1<<i]+mod)%mod;
        for(int s2=all^s1;s2;s2=(s2-1)&(all^s1)) if((s2&-s2)!=s2){
            h[s1][s2]=1;
            for(int i=0;i<n;i++) if(s2>>i&1) mul(h[s1][s2],h[s1][1<<i]);
        }
    }
    f[(k+1)%2][all][0]=1;
    for(int d=k;d>=0;d--) for(int s1=1;s1<=all;s1++){
        f[d%2][s1][0]=s1==all;
        for(int s2=s1;s2;s2=(s2-1)&s1){
            long long res=s1==all;
            for(int s3=all^s1;s3;s3=(s3-1)&(all^s1))
                res+=1ll*f[!(d%2)][s1|s3][s3]*g[s1^s2][s3]%mod*h[s2][s3]%mod;
            f[d%2][s1][s2]=res%mod;
        }
    }
    printf("%d\n",f[0][1][1]);
    return 0;
}