题目概述
随机 \(2n\) 个数，值域为 \([0,m]\)，求前 \(n\) 个数比后 \(n\) 个数大的概率（对质数 \(P\) 取模），其中 \(10^8\leq P\leq 10^9\)。
数据范围：\(1\leq n,m,T\leq 2000\)。
分析
好好玩。
显然可以转化为计数题目。
赛时想了一个 \(\mathcal{O}(Tn^2m)\) 做法。
首先我们不难想到设 \(f_{i,j}\) 表示前 \(i\) 个数和为 \(j\) 的方案。转移是简单的，求答案也是简单的：
\[ans=\sum_j\sum_{k<j} f_{n,j}\times f_{n,k}
\]
两者都可以用前缀和优化。
正解肯定不是这么乱搞的。
首先可以分成三种情况：
- 前面 \(n\) 个小于后面 \(n\) 个。
- 前面 \(n\) 个等于后面 \(n\) 个。
- 前面 \(n\) 个大于后面 \(n\) 个。
我们发现第一个和第三个其实是一样的。
于是我们的答案就是总共方案减去等于的方案再除以 \(2\)。
我们发现等于的方案很难去做，很难刻画。
考虑做一些精妙的转变：
将后 \(n\) 个数取反，相当于前面的数的值域为 \([0,m]\)，后面的为 \([-m,0]\)，等于就变成了相加为 \(0\)。
再将后 \(n\) 个数每个数加上 \(m\)，相当于前面的数的值域为 \([0,m]\)，后面的数也是，相加为 \(0\) 就变成了相加为 \(nm\)。
我们发现这个是好做的，至于怎么想到的，确实很难，不过灵光一现还是有可能的。
我们现在假设去掉这个限制（经典容斥片头曲），那么相当于在 \(2n\) 个非负数中得到的和为 \(nm\) 的方案。