P8189 [USACO22FEB] Redistributing Gifts G题解

123zbk · 2024-09-23 17:04:25 · 题解

令 g_S 表示连成一个置换环的方案数。然后将环合并，设 h_S 表示将集合 S 分成若干个置换环的方案数，显然有转移 h_S=\sum\limits_{T\subseteq S}g_Th_{S/T}。

只需考虑如何求出将其连成一个置换环的方案数。

暴力的 dp 就是设 dp_{i,j,k} 表示集合 i，起始点为 j，最后一个位置为 k 的方案数。

枚举下一个元素，实时判断能不能转移到以及有没有构成环即可。此时复杂度为 O(2^nn^3)，考虑优化。

注意到可以去掉起始点这一维，因为我们可以钦定集合 i 中最小的点当成起始点。

所以设 dp_{i,j} 表示从集合 i 的最小的点出发，到达 j 的方案数。接下来枚举点 k，如果 k 不在集合 i 中且从 j 能转移到 k，就可以进行转移。

对于每一个集合 S，枚举其最后一个到达的点，如果它能够回到起始点，那么就将其计算到 g_S 的贡献中。

复杂度为 O(2^nn^2+3^n)。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=19,maxm=1<<18;
int n,Q,s[maxn];
ll dp[maxm][maxn],g[maxm],h[maxm];
char c[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){
        bool flag=0;
        for(int j=0;j<n;j++){
            int x;
            cin>>x;
            x--;
            if(!flag){
                s[i]|=(1<<x); 
            }
            if(x==i) flag=1;
        }
    }
    for(int i=0;i<n;i++){
        dp[1<<i][i]=1;
    }
    for(int i=1;i<(1<<n);i++){
        int p=__lg(i&(-i));
        for(int j=p;j<n;j++){  
            if(dp[i][j]){
                for(int k=p+1;k<n;k++){ 
                    if(!(i&(1<<k)) and s[j]&(1<<k)){
                        dp[i|(1<<k)][k]+=dp[i][j];
                    }
                }
            }
        }
    }
    for(int i=1;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            int p=__lg(i&(-i));
            if(s[j]&(1<<p)){
                g[i]+=dp[i][j];
            }
        }
    }
    h[0]=1;
    for(int i=1;i<(1<<n);i++){
        for(int j=i;j;j=(j-1)&i){
            if(j&(i&(-i))){
                h[i]+=g[j]*h[i^j];
            }
        }
    }
    cin>>Q;
    while(Q--){
        cin>>c;
        int ans=0;
        for(int i=0;i<n;i++){
            if(c[i]=='H') ans|=(1<<i);
        }
        cout<<h[ans]*h[((1<<n)-1)^ans]<<"\n";
    }
    return 0;
}