题解：P8189 [USACO22FEB] Redistributing Gifts G

· · 题解

怎么都不写哈集幂喵！怎么还有 O(3^n) 喵！捅死你喵！捅死你喵！捅死你喵！捅死你喵！捅死你喵！捅死你喵！捅死你喵！捅死你喵！捅死你喵！

\Large\text{Solution}

考虑先将题意转化，观察到要求交换后的优先嘟比交换前的优先嘟高，可以直接将当前的 i 连向优先嘟比 i 高的位置，最后相当于要将相同颜色的剖成若干个环，求方案数。

然后我们设 $f_S$ 表示将 $S$ 集合剖成若干个环的方案数，那么为了不重复计数可以钦定枚举包含 $\text{highbit}(S)$ 的环进行计数。写出转移式就是： $$f_S=\sum\limits_{T\subseteq S}[\text{highbit}(S)\neq\text{highbit}(T)]f_Th_{S-T}$$ 那就随便做 $O(3^n)$ 了，好像还能过，但是你不准写这个做法。 考虑对这个 dp 进行优化。你发现去掉 $[\text{highbit}(S)\neq\text{highbit}(T)]$ 就是一个子集卷积板子。那你考虑先从小到大枚举 $\text{highbit}(S)$ 的值然后每次都跑一遍子集卷积就可以了。你算一下复杂度是 $\sum O(2^ii^2)=O(2^nn^2)$，那么总时间复杂度就是 $O(2^nn^2)$ 了。 $\Large\text{Code} 
#include<bits/stdc++.h>
#define int int64_t
using namespace std;
int n,q,a[18][18],e[18][18],f[262144],h[262144],tmp[262144],S,g[262144][18];
string str;
namespace fwt{
    int f[1048576],g[1048576],h[1048576];
    void fwtor(int n,int*f,int mul){
        for(int i=1;i<1<<n;i<<=1)
            for(int j=0,p=i<<1;j<1<<n;j+=p)
                for(int k=0;k<i;k++)
                    f[i+j+k]+=f[j+k]*mul;
    }
    void _or(int n,int*a,int*b,int*c){
        memcpy(f,a,(1<<n)*sizeof(a)),memcpy(g,b,(1<<n)*sizeof(b)),fwtor(n,f,1),fwtor(n,g,1);
        for(int i=0;i<1<<n;i++)
            h[i]=f[i]*g[i];
        fwtor(n,h,-1),memcpy(c,h,sizeof(h));
    }
}
namespace Subset{
    using namespace fwt;
    int f[19][262144],g[19][262144],h[19][262144];
    void subset(int n,int*a,int*b){
        memset(f,0,sizeof(f)),memset(g,0,sizeof(g)),memset(h,0,sizeof(h));
        for(int s=0,x;s<1<<n;s++)
            x=__builtin_popcount(s),f[x][s]=a[s],g[x][s]=b[s];
        for(int i=0;i<=n;i++){
            fwtor(n,f[i],1),fwtor(n,g[i],1);
            for(int j=0,k=i;j<=i;j++,k--)
                for(int s=0;s<1<<n;s++)
                    h[i][s]+=f[j][s]*g[k][s];
            fwtor(n,h[i],-1);
        }
        for(int s=0;s<1<<n;s++)
            if(s>>(n-1)&1)
                a[s]=h[__builtin_popcount(s)][s];
    }
}
int32_t main(){
    ios::sync_with_stdio(0),cin.tie(0),cin>>n,f[0]=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)
            cin>>a[i][j],a[i][j]--;
        for(int j=0;j<n;j++){
            if(a[i][j]==i)
                break;
            e[i][a[i][j]]=1;
        }
        h[1<<i]=g[1<<i][i]=1;
    }
    for(int s=1,p;s<1<<n;s++){
        p=__builtin_ctz(s);
        for(int i=p;i<n;i++)
            if(s>>i&1&&g[s][i]){
                if(e[i][p])
                    h[s]+=g[s][i];
                for(int j=p+1;j<n;j++)
                    if(!(s>>j&1)&&e[i][j])
                        g[s|1<<j][j]+=g[s][i];
            }
    }
    for(int m=1;m<=n;m++)
        Subset::subset(m,f,h);
    cin>>q;
    while(q--){
        cin>>str,S=0;
        for(int i=0;i<n;i++)
            S|=(str[i]=='H')<<i;
        cout<<f[S]*f[S^((1<<n)-1)]<<'\n';
    }
    return 0;
}