E - Ball Eat Chameleons
设颜色序列中有\(R\)个红球，\(B\)个蓝球，且有\(B+R=k\)
然后分类讨论：
-
\(R<B\) 无解
-
\(R>B\)
这时有一种合法方案为：\(R-B\)只变色龙只用吃一个红球，剩下的\(n-(R-B)\)只变色龙吃的红球和蓝球的数量相等且最后吃的那个球是蓝球
对于\(n-(R-B)\)只变色龙，称它们为\(bsl\)，有一种极端情况：若第\(i\)只变色龙要吃\(x_i\)个蓝球，\(x_i\)个红球，那么所有\(bsl\)一起先吃了对应的\(x_i-1\)个蓝球，再一起吃了对应的\(x_i\)个红球，最后再一起吃一个蓝球（这里的一起不是指的同时，而是指的这些操作都是相邻的）
这时，在操作期间，设当前所有变色龙吃了的红球数量为\(r\)，蓝球数量为\(b\)，那么有：
\[\max(b-r)=B-(n-(R-B))=R-n \]所以，我们就可以将操作抽象为从\((0,0)\)开始，每次可以移动一个单位向量\((0,1)\)或\((1,0)\)，求从\((0,0)\)移动到\((R,B)\)且不经过\(y=x+(R-n+1)\)的方案数
因为\(y=x+(R-n)\)是合法的，所以要\(+1\)
于是就是经典的翻折，答案为总方案数减去将终点关于直线对称后的新的终点的方案数
\[C_{R+B}^R-C_{R+B}^{2R-n+1} \]将点\((a,b)\)关于直线\(y=x+T\)对称后的点为\((b-T,a+T)\)
- \(R=B\)
这时，所有的变色龙都吃了相等数量的红球和蓝球，且最后一个吃的是蓝球，所以这时的颜色序列的最后一个颜色一定为蓝色
所以，若我们去掉颜色序列的最后一个蓝球，就又变成了：\(k-1\)个球，且有\(R>B（R=B+1）\)
所以我们只需要枚举\(R\)即可
复杂度\(O(K)\)
#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353,N=5e5+5;
int n,k,ans;
int jc[N],invf[N];
int power(int x,int y){
int ans=1;
for(;y;y>>=1,x=1ll*x*x%MOD) if(y&1) ans=1ll*ans*x%MOD;
return ans;
}
void Init(){
jc[0]=1;
for(int i=1;i<=k;++i) jc[i]=1ll*jc[i-1]*i%MOD;
invf[k]=power(jc[k],MOD-2);
for(int i=k-1;i>=0;--i) invf[i]=1ll*invf[i+1]*(i+1)%MOD;
}
int C(int n,int m){
if(m>n) return 0;
return 1ll*jc[n]*invf[n-m]%MOD*invf[m]%MOD;
}
int main(){
scanf("%d%d",&n,&k);
if(k<n) return printf("0"),0;
Init();
for(int r=k+1>>1,b;r<=k;++r){
b=k-r;
if(b==r) --b;
ans=(1ll*ans+((1ll*C(r+b,r)-1ll*C(r+b,(r<<1)-n+1))%MOD+MOD)%MOD)%MOD;
}
printf("%d",ans);
return 0;
}