T1. candy
T2. 清仓甩卖（sale）
https://www.luogu.com.cn/problem/P14636
对合法情况计数有些困难，考虑 hxf 容斥（整体 - 不合法）。
容易观察到不合法情况只可能是用 \(2\) 换 \(1\)，于是形态只可能是如下图所示（图中元素按性价比排序）。
\(j\) 是红线前面部分的最后一个 \(1\)，\(k\) 是红线后面部分的第一个 \(1\)，也就是说 \(j, k\) 之间没有其他的 \(1\) 了。
考虑对一组 \((i, j, k)\) 计算贡献。
由于本题中存在 \(a_i\) 相同的情况，我们先把 \(a_i\) 都认为是一个二元组 \((a_i, i)\)，这样方便比较大小。以下我们认为二元组 \((p_1, q_1) > (p_2, q_2)\) 当且仅当 \(p_1 > p_2\) 或 \(q_1 < q_2\)，小于号同理。
首先考虑合法条件，根据题目要求有 \(a_i > a_j, 2a_j \le a_i\)，能用 \(i\) 换掉 \(j\) 和 \(k\) 当且仅当 \(a_j + a_k < a_i\).
根据上面的条件，把序列按 \(a_i\) 降序排序后，它们在序列中的先后顺序一定是 \(i, j, k\).
考虑除了 \(i, j, k\) 以外的位置 \(p\).
- 若 \(a_p < a_k\)，则 \(w_p\) 如何取值都不影响，所以有贡献 \(2^{n-k}\).
- 若 \(a_k < a_p < a_j\)，则 \(w_p\) 不能取 \(1\)，否则就会在中间的全 \(2\) 段多出一个 \(1\)，与条件相悖。所以这部分一定有 \(w_p = 2\). 是固定的，所以不会产生贡献。
- 若 \(a_j < a_p < a_i\)，由于红线右侧就是一个性价比为 \(\frac{a_i}{2}\) 的东西，所以如果取 \(w_p=2\) 就会直接掉到红线后面；而如果取 \(w_p=1\) 就会留在 \(j\) 左侧，占用 \(1\) 的容量。相当于选择它占用 \(0\) 还是 \(1\) 的容量。
- 若 \(a_p > a_i\)，无论它怎么选都会留在红线左侧，所以相当于选择占用 \(1\) 还是 \(2\) 的容量。
由于序列已经按 \(a_i\) 降序排序了，第三类、第四类数的个数分别为 \((j-i-1)\)、\((i-1)\).
枚举有 \(s\) 个第四类数选了 \(w_p = 1\)，剩下的第四类数就是 \(w_p = 2\) 的，那么还剩 \(m-2-s-2(i-1-s)=(m-2i+s)\) 的容量留给第三类数。
于是总方案数是 \(\displaystyle 2^{n-k} \times \sum_{s=0}^{i-1} {i-1 \choose s} {j-i-1 \choose m-2i+s}\).
但其实还有一个 corner case：就是 \(i\) 后面没有任何一个 \(1\)，这时候要满足的条件就变成了 \(a_j < a_i\)，单独加上 \(\displaystyle \sum_{s=0}^{i-1} {i-1 \choose s} {j-i-1 \choose m-2i+s}\) 的贡献即可。
到这里就可以写出一个 \(O(n^3)\) 的做法。可以拿到 \(72\) 分。
考虑进一步优化。注意到按 \(a_i\) 降序排序后对于固定的 \(i, j\)，满足条件的 \(k\) 是一段后缀 \([k', n+1]\)（\(k=n+1\) 表示不存在这样的 \(k\)）。这段后缀里的贡献形如 \(\displaystyle \sum_{s=0}^{i-1} {i-1 \choose s} {j-i-1 \choose m-2i+s} \times \left(\sum_{k=k'}^n 2^{n-k} +1\right)\).
后面的部分其实就是 \(2^{n-k'+1}\).
于是答案即为
注意到这是范德蒙德卷积的形式，于是可以化成 \(\displaystyle {(i-1)+(j-i-1) \choose i+j-m-1} = {j-2 \choose i+j-m-1}\).
void solve()
{cin >> n >> m;tot = 1, ans = 0;for(int i = 1; i <= n; i++) tot = tot * 2ll % mod;for(int i = 1; i <= n; i++) cin >> a[i], cs[i] = 0;sort(a + 1, a + n + 1, greater<int>());for(int i = 1; i <= n; i++)for(int p = 1; p <= n; p++)cs[i] += (a[p] > a[i] || (a[p] == a[i] && p < i));for(int i = 1; i <= n; i++) // 2 的位置for(int j = 1, k = n + 1; j <= n; j++){if(!(2 * a[j] > a[i]) || i == j || a[i] <= a[j]) continue;while(k > 1 && a[k - 1] + a[j] < a[i]) k--;int c2 = 0, c3 = 0, res = 0;c2 = i - 1, c3 = j - i - 1;cadd(ans, C(j - 2, i + j - m - 1) * pw[n - k + 1] % mod);}cout << ((tot - ans) % mod + mod) % mod << '\n';return;
}