[CF1842H]Tenzing and Random Real Numbers
题面
原题传送门
题面机翻
有 \(n\) 个介于 0 和 1 之间（包括 0 和 1）的均匀随机实变量，记为 \(x_1, x_2, \ldots, x_n\) 。
Tenzing有 \(m\) 个条件。每个条件的形式为 \(x_i+x_j\le 1\) 或 \(x_i+x_j\ge 1\) 。
Tenzing想要知道所有条件都满足的概率，模为 \(998~244~353\) 。
形式上，设为 \(M = 998~244~353\) 。可以证明答案可以用不可约分数 \(\frac{p}{q}\) 表示，其中 \(p\) 和 \(q\) 是整数，而 \(q \not \equiv 0 \pmod{M}\) 是不可约分数。输出等于 \(p \cdot q^{-1} \bmod M\) 的整数。换句话说，输出 \(0 \le x < M\) 和 \(x \cdot q \equiv p \pmod{M}\) 的整数 \(x\) 。
题目描述
There are $ n $ uniform random real variables between 0 and 1, inclusive, which are denoted as $ x_1, x_2, \ldots, x_n $ .
Tenzing has $ m $ conditions. Each condition has the form of $ x_i+x_j\le 1 $ or $ x_i+x_j\ge 1 $ .
Tenzing wants to know the probability that all the conditions are satisfied, modulo $ 998244353 $ .
Formally, let $ M = 998244353 $ . It can be shown that the answer can be expressed as an irreducible fraction $ \frac{p}{q} $ , where $ p $ and $ q $ are integers and $ q \not \equiv 0 \pmod{M} $ . Output the integer equal to $ p \cdot q^{-1} \bmod M $ . In other words, output the integer $ x $ that $ 0 \le x < M $ and $ x \cdot q \equiv p \pmod{M} $ .
动态规划
首先转化题意，令\(x_i+x_j\leq1\)变为\(y_i+y_j\leq 0\)，\(x\in[0,1]\rightarrow y\in[-\frac{1}{2},\frac{1}{2}]\)。而无论是\(x\)还是\(y\)，在计算概率时是等效的。
现在考虑式子\(y_i+y_j\leq 0\)，由于顺序不影响，不妨设\(|y_i|\leq|y_j|\)，则原式成立当且仅当\(y_j\leq 0\)。反过来说，若想令\(y_j\leq 0\)，那么\(y_i+y_j\leq 0\)必须成立，不能存在\(y_i+y_j\geq 0\)。（\(\geq\)的情况同理）
于是我们可以得到\(y_i\)为正/负的时候，不能存在的编号。（以\(y_i\)的绝对值最大为前提）
其实用\(x\)也是一样的，考虑其对于\(\frac{1}{2}\)的大小状况。
状态定义
\(f(S)\)表示只考虑集合\(S\)中的编号，且集合中数字按照绝对值大小加入的情况下，它们满足条件的概率。
\(g(i,0/1)\)表示当\(y_i\)小于（或大于）\(0\)时，不能存在的编号的集合。（以\(y_i\)的绝对值最大为前提）
状态转移方程
枚举最后一个加入集合\(S\)的数的编号。
其中\(S\subseteq [1,n]\)。
边界条件
\(f(\empty) = 1\)
答案
由于存在取模，统计答案时用逆元代替除法。