【题解】[USACO22FEB] Redistributing Gifts G

7KByte · 2022-04-09 10:50:24 · 题解

有个很奇妙的 \mathcal{O}(n^22^n) 的做法。

首先题目等价于将给定图划分成若干个简单环，所以我们可以设计 DP 状态，f_{x,S} 表示以 x 结尾，经过节点为 S，以 S 中最小的点出发的路径方案，如果 x 到最小点有边，就更新 h_{S} 表示点集为 S 的环的方案。

然后我们再合并环，g_{S} 表示将集合 S 划分成若干环的方案，然后枚举最小点所在的环 T，有转移 g_{S} = \sum \limits_{T\subseteq S} h_{T}g_{S/T}，这样就可以做到 \mathcal{O}(n^22^n + 3^n)。

我一度认为 3^n 是信息极限了，但是这题还有一些特殊性质。

我们观察到由 h 可以直接推出 g，那么我们是否可以跳过 h 这一步，直接由 f\to g。

那么我们更新一下状态，f_{x, S} 表示已经 fix 了若干个环，然后当前路径是从 S 中最小的点出发到 x 结束的方案数，这样 f_{x,S} 可以直接转移到 g_{S}。

但是这样 f 就需要考虑新开一个环的可能，所以我们再从 g\to f ，枚举比 g_{S} 中最小的点更小的点 x 作为起点，然后 g_{S} \to f_{x, S\cup\{x\}}。为什么要更小的点，因为避免一个划分方案重复统计，以环的最小的点为关键字从大到小依次考虑。

这样时间复杂度是 \mathcal{O}(n^22^n)。代码和上面描述有点区别，是以环的最大点作为关键字从小到大考虑，本质相同。

#define N 18
int n, a[N][N], e[N][N], bt[1 << N]; char ch[N + 5]; LL f[N][1 << N], g[1 << N];

int main() {
    read(n);
    rep(i, 0, n - 1){
        rep(j, 0, n - 1)read(a[i][j]), a[i][j] --;
        rep(j, 0, n - 1){
            e[i][a[i][j]] = 1;
            if(a[i][j] == i)break;
        }
    }
    int w = (1 << n) - 1;
    bt[0] = ~0; rp(i, w)bt[i] = bt[i >> 1] + 1;
    g[0] = 1;
    rep(s, 0, w){
        int k = bt[s];
        rep(i, 0, k){
            if(e[i][k])g[s] += f[i][s];
            rep(j, 0, k)if(!((s >> j) & 1) && e[i][j])
                f[j][s | (1 << j)] += f[i][s];
        }
        rep(i, k + 1, n - 1)f[i][s | (1 << i)] += g[s];
    }
    int T; read(T);
    while(T--){
        scanf("%s", ch);
        int s = 0;
        rep(i, 0, n - 1)if(ch[i] == 'H')s |= 1 << i;
        printf("%lld\n", g[s] * g[w ^ s]);
    }
    return 0;
}