CF1842H Tenzing and Random Real Numbers 题解

题目链接

点击打开链接

题目解法

实数的概率好反直觉！

对 \(1\) 做限制不是很好做，考虑变成正负性的限制（即对 \(0\) 做限制）
令 \(y_i=x_i-0.5\)，那么限制就变成了 \(y_i+y_j\le 0,\;y_i+y_j\ge 0\)

这里要给出一些实数概率的结论：

1. 实数下，\(x=y\) 的概率为 \(0\)，因为 \(\frac{1}{\infty}=0\)
2. 对于任意一组 \(x\) 之间的范围相同的 \(x_1,...,x_n\)，那么对于每一个大小关系 \(x_1<x_2<...<x_n\)，概率是相等的

有了这两个结论，不难得到做法
考虑状压 \(y_i\) 的大小关系，同时需要得出 \(y_i\) 的正负（\(0\) 不用管，因为取到 \(0\) 的概率为 \(0\)），最后把方案数除以 \(n!2^n\) 就是答案
状压 \(dp\) 设计简单，这里不讲了
暴力做是 \(O(2^nn^2)\)，不难用位运算优化到 \(O(2^nn)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=20,P=998244353;
int n,m,f[1<<N],lmt[2][N];
int qmi(int x,int y){
    int res=1;for(;y;y>>=1){ if(y&1) res=1ll*res*x%P;x=1ll*x*x%P;}
    return res;
}
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
int main(){
    read(n),read(m);
    F(i,1,m){
        int op,x,y;read(op),read(x),read(y);x--,y--;
        lmt[op][x]|=1<<y,lmt[op][y]|=1<<x;
    }
    f[0]=1;
    F(S,1,(1<<n)-1)
        F(i,0,n-1) if(S>>i&1){
            int p=S&lmt[0][i],q=S&lmt[1][i];
            if(p&&q) continue;
            if(!p&&!q) inc(f[S],2*f[S^(1<<i)]%P);else inc(f[S],f[S^(1<<i)]);
        }
    int tot=1<<n;F(i,1,n) tot=1ll*tot*i%P;
    int ans=1ll*f[(1<<n)-1]*qmi(tot,P-2)%P;
    printf("%d\n",ans);
    return 0;
}