咦？为什么我不会范德蒙德卷积呢？为什么NOIP会考范德蒙德卷积呢？我的意思是我这样的数学苦手怎么可能在考场上直接发明出这种级别的组合数结论呢？那你考考我，那你考考我之前就不能先让我学会再考吗？
T1美丽挂分中，请你写拍子，请你写拍子喵喵喵
T2
P14636 NOIP2025 清仓甩卖
首先记得看完题先看样例，因为这道题的题意确实不能算是清晰，说到不清晰，我的意思是20年内没人能不看样例解释看懂这个题面，真的。
直接统计合法方案数好恶心，而且感觉一下确实不合法方案要比合法方案少得多，考虑容斥统计不合法方案数。对于一种方案不合法，相当于存在一个 122...221 的段，其中首尾的1能买但是中间某个2不能买，这个2的原价还比那两个1原价加起来还高，的确是一个严格的限制，严格=好刻画。
考虑枚举两个数，最后没选的那个2和前面先碰见的1，然后直接计算最后碰见的1。
直接对序列排个序，从小到大，那么这三个数的大小关系如下，其中 \(x1\) 表示先碰见的1，\(y1\) 表示后碰见的1，\(a\) 表示2：
大概就是这样，至于 \(\frac a2\) 的位置好像可以直接二分，或者双指针。接下来的问题是枚举完怎么统计方案。
对于 \(y1\)，注意到随着 \(x1\) 递增，这玩意一定是一个逐渐减少的前缀，直接双指针刻画。
然后可以发现截止 \(\frac a2\) 的位置，之前碰到的数贡献必须是正好 \(m-1\) 才行，这个东西怎么刻画呢？考虑排序后的序列中 \(x1\) 的位置 \(j\) 和 \(a\) 的位置 \(i\)，对于 \(i\) 和 \(j\) 之间的 \(i-j-1\) 个数字，定价2相当于移到 \(\frac a2\) 的前面，不做贡献，定价1才有贡献，而 \(i\) 之后的 \(n-i\) 个数字，则两种选法均有贡献，那么令 \(k\) 表示当前序列全选1时，和期望的 \(m-1\) 相差的数量，而方案数就相当于先把 \(k\) 补齐，然后每有额外的一个数不做贡献，就要有一个数做2的贡献，基本上，就是下面的这个式子，其中 \(x,y\) 分别代表 \(i\) 与 \(j\) 之间的数字个数或者 \(i\) 之后的数字个数，取决于当前相对于 \(m-1\) 多了还是少了：
我的妈呀！眼尖的人一眼就看出来这是一个范德蒙德卷积，这是一个范德蒙德卷积！！！然后用一秒钟的时间把它化成 \(\binom{x+y}{x+k}\) 然后直接做完了，但是我的妈呀！我怎么没学过这个烦什么什么德卷积，怎么办？！
此时我们还有一个简单易懂的组合意义推出来，好妙，学不会啊学不会
直接把后面那一坨贡献为1或2的全部减1，使得所有点都为0或1，那么相当于 \(x+y\) 个数中选择 \(m-x-1\) 个，此时我们认为 \(x\) 表示 \(i\) 后面的一些数。直接就得到了 \(\binom{x+y}{m-x-1}\) 的优美式子，根据之前 \(k\) 的意义，这两个式子实则一样。
追加一下范德蒙德卷积推出这个的过程：
令 \(j=i+k\) 得
\[\sum\binom x{j-k}\binom yj \]注意到这个 \(k\) 是负的好难看，直接把它变成正的
\[\sum\binom x{x-j+k}\binom yj \]那你不就推出来了
\[\binom{x+y}{x+k} \]
werwerwer数学怎么这样数学werwerwer
还能赢吗？还能赢的，被这玩意搞退役是不可能的。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll p = 998244353;
ll c,t,n,m,a[5010],fac[5010],inv[5010],ans,pw[5010];
ll qkp(ll x,ll y)
{ll res = 1;while(y){if (y&1) res = res*x%p;y >>= 1;x = x*x%p;}return res;
}
ll C(ll n,ll m)
{if (n < 0 || m < 0 || n < m) return 0;return fac[n]*inv[m]%p*inv[n-m]%p;
}
inline int read()
{int x = 0;char ch = getchar();while(ch<'0'||ch>'9') ch = getchar();while(ch>='0'&&ch<='9'){x = (x<<1)+(x<<3)+(ch^48);ch = getchar();}return x;
}
int main()
{read(); t = read(); fac[0] = pw[0] = 1;for (int i = 1;i <= 5000;i++) fac[i] = fac[i-1]*i%p;inv[5000] = qkp(fac[5000],p-2);for (int i = 5000;i;i--) inv[i-1] = inv[i]*i%p;for (int i = 1;i <= 5000;i++) pw[i] = pw[i-1]*2%p;while(t--){n = read(); m = read(); ans = 0;for (int i = 1;i <= n;i++) a[i] = read()*2;sort(a+1,a+n+1);for (ll i = 1,l = 1;i <= n;i++){while(a[i]>>1 >= a[l]) l++;ll pt = l-1,tmp = 1;for (int j = 1;j < l;j++) tmp = (tmp+pw[j-1])%p;for (int j = l;j < i;j++){while(a[pt]+a[j] >= a[i] && pt >= 0) tmp = (tmp-pw[max(pt-1,0ll)]+p)%p,pt--;ll k = m-n+j-1;if (k > 0) ans = (ans+C(n-j-1,i-j-1+k)*tmp%p)%p;else ans = (ans+C(n-j-1,n-i-k)*tmp%p)%p;}}cout << (qkp(2,n)-ans+p)%p << "\n";}return 0;
}