NOI2021D1T2 是 LGV 板板题，震撼。
ABC216H Random Robots
考虑转化题意：有 (k) 个起点 ((x_1,0),(x_2,0),cdots,(x_k,0))，(n) 轮，每轮所有位置 ((x,y)) 都会等概率走到 ((x+1,y+1)) 与 ((x,y+1))，求路径不相交的概率。（显然等价于方案数）
这个东西明示我们使用 LGV 引理，考虑 dp 求解，设 (f(S,t)) 为考虑集合 (S)，终点的 (x) 最大值为 (t) 的答案：
[f(S,t)=sum_{0leqslant y_1<y_2<cdots<y_{|S|}leqslant t}left|egin{matrix}w(x_{S_1},y_1)&w(x_{S_1},y_2)&cdots&w(x_{S_1},y_{|S|})\w(x_{S_2},y_1)&w(x_{S_2},y_2)&cdots&w(x_{S_2},y_{|S|})\vdots&vdots&ddots&vdots\w(x_{|S|},y_1)&w(x_{|S|},y_2)&cdots&w(x_{|S|},y_{|S|})end{matrix}
ight|
]
其中 (w(x,y)={nchoose y-x})。
当 (y_k<t) 时
[f(S,t)leftarrow f(S,t-1)
]
当 (y_k=t) 时
[f(S,t)leftarrowsum_{i=1}^{|S|}(-1)^{|S|+i}w(x_{S_i},t)f(S-{S_i},t-1)
]
然后直接状压 dp 即可，时间复杂度：(O(2^kk(n+max{x_i})))。
#include<stdio.h>
const int maxk=1<<10,maxn=2005,mod=998244353,inv2=(mod+1)/2;
int n,k,ans,mulinv2;
int x[maxn],bitcnt[maxk],f[maxk][maxn],C[maxn][maxn],mul[2];
int main(){
scanf("%d%d",&k,&n);
for(int i=1;i<=k;i++)
scanf("%d",&x[i]);
mul[0]=1,mul[1]=mod-1;
for(int i=0;i<=n;i++){
C[i][0]=C[i][i]=1;
for(int j=1;j<i;j++)
C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
mulinv2=1;
for(int i=1;i<=n;i++)
mulinv2=1ll*mulinv2*inv2%mod;
for(int i=1;i<(1<<k);i++)
bitcnt[i]=bitcnt[i>>1]+(i&1);
f[0][0]=1;
for(int i=0;i<=x[k]+n;i++){
for(int j=0;j<(1<<k);j++)
f[i+1][j]=f[i][j];
for(int j=0;j<(1<<k);j++)
for(int p=1;p<=k;p++)
if(((j>>(p-1))&1)==0&&x[p]<=i&&i-x[p]<=n)
f[i+1][j|(1<<(p-1))]=(f[i+1][j|(1<<(p-1))]+1ll*f[i][j]*mul[bitcnt[j>>(p-1)]&1]%mod*C[n][i-x[p]]%mod*mulinv2)%mod;
}
printf("%d
",f[x[k]+n+1][(1<<k)-1]);
return 0;
}