看了题解。好难受，想用积分求概率，算了半天。发现没啥规律，不是不能算，就是太可怕了。
Problem
有 \(n\) 个 \([0,1]\) 范围内的均匀随机变量 \(x_{1\cdots n}\) 和 \(m\) 条限制，每条限制形如 \(x_i+x_j\le 1\) 或 \(x_i+x_j\ge 1\)。请你求出所有限制均满足的概率。对 \(998244353\) 取模。
\(1\le n\le 20,\ 0\le m\le n^2+n\)。
Solution
设 \(y_i=x_i-\frac{1}{2}\)。这样的好处是，消去常数，我们有如下的性质：
- 若 \(x_i+x_j<1\Rightarrow y_i+y_j<0\)，那么它们同为负或者负数的绝对值大于正数。不妨 \(|y_i|<|y_j|\)，那么就是 \(y_j<0\)。
- 将小于换成大于也一样。
这启发我们按照 \(|y_i|\) 大小考虑。考虑一个集合 \(S\)，现在加入 \(y_i\)，那么发现 \(y_i\) 能不能加入，符号是正是负，只和它自己有关。那么状压 DP 就是了。
话说这里有个小细节：\(y_i\) 比 \(y_1,y_2,\cdots,y_{i-1}\) 都大的概率是 \(\frac{1}{i}\)。可以考虑算方案数，最后除以总方案数的时候会发现有个阶乘，那么把这个阶乘分发到每个加入的地方即可。或者好像有神秘微积分证明。
Code
点击查看代码
// LUOGU_RID: 115883767
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
const int P=998244353;
LL red(LL&x){x%=P;}
LL mod(LL x){return (x%P+P)%P;}
int getbit(int k){return 1<<k;}
bool conbit(int x,int k){return x&getbit(k);}
int n,m;
LL qpow(LL a,LL b,int p=P){LL r=1;for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p; return r;}
LL inv[30],f[1<<20],Ele[30],Ege[30];
int main(){
// #ifdef LOCAL
// freopen("input.in","r",stdin);
// #endif
for(int i=1;i<=25;i++) inv[i]=qpow(i,P-2,P);
scanf("%d%d",&n,&m);
for(int i=1,t,u,v;i<=m;i++){
scanf("%d%d%d",&t,&u,&v),u--,v--;
if(!t) Ele[u]|=1<<v,Ele[v]|=1<<u;
else Ege[u]|=1<<v,Ege[v]|=1<<u;
}
f[0]=1;
for(int S=0;S<1<<n;S++){
for(int i=0;i<n;i++){
if(conbit(S,i)) continue;
if((Ege[i]&(S|1<<i))==0) red(f[S|1<<i]+=f[S]);
if((Ele[i]&(S|1<<i))==0) red(f[S|1<<i]+=f[S]);
}
}
LL ans=f[(1<<n)-1];
for(int i=1;i<=n;i++) red(ans*=inv[i]*inv[2]%P);
printf("%lld\n",ans);
return 0;
}