Tenzing and Random Real Numbers

Little09 · 2023-07-11 13:13:25 · 题解

首先看限制 x_i+x_j\le 1，这右边有个常数的很难受，那我们定义 y_i=x_i-0.5，也就是 x_i=y_i+0.5，那么代入原式得到的是 y_i+y_j\le 0，其中 y_i 在 [-0.5,0.5] 中随机。

对于 y_i+y_j\le 0 而言，不妨假设 |y_i|\le|y_j|，那么我们发现条件 y_i+y_j\le 0 成立等价于 y_j\le 0。这启发我们按照 |y_i| 的从小到大顺序做 DP。

我们需要求的概率，其实就是计数有多少个将 |y_i| 排列的方案，并给每个 |y_i| 选择一个正负号的方案，再除以 n!2^n。这个问题我们直接状压 DP，dp_S 表示目前已考虑 S 集合，转移的时候考虑当前加入的是哪个 |y_i|，再枚举一下正负号，检查一下前面的条件是否都满足，暴力检查是 O(2^nn^2)，也可以通过。稍微用位运算记录一下就是 O(2^nn) 的。

const int N=20,M=(1<<N);
int n,m; 
int g[N][N],dp[M],e[N][2];
ll ksm(ll x,ll y)
{
    ll res=1;
    while (y)
    {
        if (y&1) res=res*x%mod;
        x=x*x%mod,y>>=1;
    }
    return res;
}
void add(ll &x,ll y)
{
    x+=y;
    if (x>=mod) x-=mod;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    rep(i,1,m)
    {
        int tp,x,y;
        cin >> tp >> x >> y;
        x--,y--;
        e[x][tp]|=(1<<y),e[y][tp]|=(1<<x);
    }
    dp[0]=1;
    rep(i,1,(1<<n)-1)
    {
        rep(j,0,n-1)
        {
            if ((i&(1<<j))==0) continue;
            rep(k,0,1)
            {
                if (e[j][1-k]&i) continue;
                (dp[i]+=dp[i^(1<<j)])%=mod;
            }
        }
    }
    ll ans=dp[(1<<n)-1];
    rep(i,1,n) ans=ans*ksm(i,mod-2)%mod;
    ans=ans*ksm(inv2,n)%mod;
    cout << ans;
    return 0;
}