点此看题面

大致题意： 有\(S\)张无编号的牌，可以将任意张牌锻造成\(n\)种步兵或\(m\)种弩兵中的一种，求最后步兵数量大于等于\(l\)小于等于\(r\)的方案数。

暴力式子

首先我们来考虑暴力式子。

假设我们确定了要选\(x\)个步兵数量，然后要求出此时的方案数。

则我们就要使用隔板法。

仔细思考，其实我们就相当于要求出把\(x\)个步兵分成\(n\)组和把\(S-x\)个步兵分成\(m+1\)组的方案数的乘积。（其中\(m+1\)组指的是\(m\)种弩兵以及不锻造这\(m+1\)种情况）

而这两个要求的东西本质上是一样的。

以把\(x\)个步兵分成\(n\)组为例，考虑到这是无编号的，因此我们完全可以假设每个步兵被分到的组号是递增的。

那也就是说，我们要求把一个长度为\(x\)的序列分割成\(n\)部分（可以为空）的方案数。

而分割成\(n\)部分，就相当于加入了\(n-1\)块隔板。

如果把隔板也看做序列的一部分，则序列总长度就变成了\(x+n-1\)，而分割就相当于要在这个序列中选出\(n-1\)个位置。

因此方案数就是：

同理，把\(S-x\)个步兵分成\(m+1\)组的方案数就是：

于是它们的乘积就是：

而最终答案就是：

抽象问题到二维平面

我们可以发现，这其实就相当于从\((0,0)\)走到\((S,n+m)\)，且必须经过点\((l,n)\)下方，不能经过点\((r+1,n)\)下方的方案数。

这其实就相当于用经过点\((l,n)\)下方的方案数减去经过点\((r+1,n)\)下方的方案数。

应该还是比较简单的。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 10000000

#define X 998244353

#define max(x,y) ((x)>(y)?(x):(y))

#define Inc(x,y) ((x+=(y))>=X&&(x-=X))

using namespace std;

int n,m,s,l,r,Inv[(N<<1)+5],p1[N+5],p2[N+5];

I int C(CI x,CI y)//求组合数

{

	if(x<y||x<0) return 0;RI i,res=1;//判断越界

	for(i=1;i<=y;++i) res=1LL*res*(x-i+1)%X*Inv[i]%X;//统计答案

	return res;//返回答案

}

I int Calc(CI x)//计算经过点(x,n)下方的方案数

{

	RI i,res=0;for(p1[0]=i=1;i^n;++i) p1[i]=1LL*p1[i-1]*(x-1+i)%X*Inv[i]%X;//计算p1

	for(p2[n-1]=C(s-x+m+1,m+1),i=n-2;~i;--i) p2[i]=1LL*p2[i+1]*(s-x+n+m-i)%X*Inv[n+m-i]%X;//计算p2

	for(i=0;i^n;++i) Inc(res,1LL*p1[i]*p2[i]%X);return res;//统计答案

}

int main()

{

	RI i,lim;scanf("%d%d%d%d%d",&n,&m,&s,&l,&r);

	for(Inv[0]=Inv[1]=1,i=2,lim=max(n,m)<<1;i<=lim;++i) Inv[i]=1LL*(X-X/i)*Inv[X%i]%X;//线性求逆元

	return printf("%d",(Calc(l)-Calc(r+1)+X)%X),0;//输出答案

}