[ABC235G] Gardens

Problem Statement

Takahashi has $A$ apple seedlings, $B$ banana seedlings, and $C$ cherry seedlings. Seedlings of the same kind cannot be distinguished.
He will plant these seedlings in his $N$ gardens so that all of the following conditions are satisfied.

• At least one seedling must be planted in every garden.
• It is not allowed to plant two or more seedlings of the same kind in the same garden.
• It is not necessary to plant all seedlings he has.

How many ways are there to plant seedlings to satisfy the conditions? Find the count modulo $998244353$.
Two ways are distinguished when there is a garden with different sets of seedlings planted in these two ways.

Constraints

• $1 \leq N \leq 5 \times 10^6$
• $0 \leq A \leq N$
• $0 \leq B \leq N$
• $0 \leq C \leq N$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $A$ $B$ $C$

Output

Print the answer.

Sample Input 1

2 2 1 1

Sample Output 1

21

As illustrated below, there are $21$ ways to plant seedlings to satisfy the conditions.
(The two frames arranged vertically are the gardens. $A, B, C$ stand for apple, banana, cherry, respectively.)

如果不考虑每个花园中都要种种子的限制，怎么做？

枚举总共会泼洒几个苹果的种子，几个香蕉的种子，几个樱桃的种子，然后用组合数进行计算。用表达式来写就是 \((\sum\limits_{i=0}^aC_n^i)(\sum\limits_{i=0}^bC_n^i)(\sum\limits_{i=0}^cC_n^i)\)

为了方便，设 \(S(n,m)=\sum\limits_{i=0}^mC_n^i\)，上面的表达式可以写作 \(S(n,a)\times S(n,b)\times S(n,c)\)

现在要加上每个花园中都要种种子的条件，明显用容斥原理。

定义 \(f(i)\) 为至多有 \(i\) 个花园中有种子的情况数，那么最终答案为 \(f(n)-f(n-1)+f(n-2)-\cdots\)

我们需要快速算出 \(S(n,m)\)，但这不太可能有很好的通项公式。如果 \(n\) 为定值，那就处理一个前缀和就可以了，但现在 \(n\) 不为定值， \(m\) 才是。考虑杨辉三角的转移公式，我们可以发现从 \(S(n,m)\) 到 \(S(n+1,m)\) 的路程中，除了 \(C_n^m\)，全部算了两次。可以得到转移式子 \(S(n,m)=S(n-1,m)+C_{n-1}^m\)。所以计算 \(m=a,b,c\) 时的答案，套容斥式子就可以了。

#include<cstdio>
const int P=998244353,N=5e6+5;;
int n,a,b,c,f[N],fa[N],fb[N],fc[N],inv[N],iv[N],ans;
int calc(int x,int y)
{
	if(x<y)
		return 0;
	return 1LL*f[x]*iv[y]%P*iv[x-y]%P;
}
int main()
{
	scanf("%d%d%d%d",&n,&a,&b,&c);
	iv[0]=iv[1]=inv[1]=f[0]=f[1]=1;
	for(int i=2;i<=n;i++)
	{
		inv[i]=1LL*(P-P/i)*inv[P%i]%P;
		iv[i]=iv[i-1]*1LL*inv[i]%P;
		f[i]=f[i-1]*1LL*i%P;
	}
	fa[0]=fb[0]=fc[0]=1;
	for(int i=1;i<=n;i++)
	{
		fa[i]=(fa[i-1]*2LL-calc(i-1,a)+P)%P;
		fb[i]=(fb[i-1]*2LL-calc(i-1,b)+P)%P;
		fc[i]=(fc[i-1]*2LL-calc(i-1,c)+P)%P;
//		printf("%d %d %d\n",fa[i],fb[i],fc[i]);
	}
	for(int i=0;i<=n;i++)
		(ans+=(i&1? -1LL:1LL)*calc(n,i)*fa[n-i]%P*fb[n-i]%P*fc[n-i]%P)%=P;
	printf("%d",(ans+P)%P);
}