Description

abc225h

Solution

First, consider not distinguishing the remaining \ (m-k \) individuals, only their positions, and finally multiply the answer by \ ((m-k)! \)
Consider calculating three values,

1. There are \ (len \) consecutive chairs. There are people before the first chair and after the last chair. There are \ (k \) people to sit. The weight sum of all schemes
2. There are \ (len \) consecutive chairs. There are people before the first chair and \ (k \) people to sit. The weight sum of all schemes
3. There are \ (len \) consecutive chairs and \ (k \) individuals to sit. The weight sum of all schemes

Calculate the first one first
It is not difficult to find that this formula is to split \ (len+1 \) into \ (k+1 \) ordered positive integers, and the product sum of these positive integers
Now the calculation splits \ (n \) into \ (k \) ordered positive integers
Then you can directly write out the generating function of the answer \ (f (x) = (\ sum \ limits {i}ix ^ I) ^ k \),
The required answer is \ (F(x)[x^n] \)
Consider writing out the closed form of \ (\ sum \ limits {ui}ix ^ I \)
\(\begin{aligned}\sum\limits_iix^i&=x\sum\limits_iix^{i-1}\\&=x\sum\limits_i(x^i)'\\&=x(\frac{1}{1-x})'\\&=\frac{x}{(1-x)^2}\end{aligned}\)
Then there are \ (\ displaystyle F(x)=(\frac{x}{(1-x)^2})^k=\frac{x^k}{(1-x)^{2k} \)
Then the answer is \ (\ displaystyle F(x)[x^n]=\frac{x^k}{(1-x)^{2k}}[x^n]=\frac{1}{(1-x)^{2k}}[x^{n-k}] \)
And \ (\ displaystyle \ frac {1} {(1-x) ^ {2K} = \ sum \ limits_i \ binom {I + 2k-1} {I} x ^ I \)
So the answer is \ (\ displaystyle \binom{n+k-1}{n-k} \)
Then the first value is \ (\ displaystyle \binom{len+k+1}{2k+1} \)

Now calculate the second value
Consider enumerating the location of the last person \ (i \), and the rest will become the first value
That is \ (\ displaystyle \ sum \ limits {I = k} ^ {len} \ binom {I-1 + k-1 + 1} {2 (k-1) + 1} = \ sum \ limits {I = k} ^ {len} \ binom {I + k-1} {2k-1} = \ binom {len + K} {2K} \)

Now calculate the third value
Consider enumerating the length of the last sequence, and the rest will become the first value
Namely
\(\displaystyle\begin{aligned}&\sum\limits_{i=k}^{len}(len-i+1)\binom{i-2+k-2+1}{2*(k-2)+1}\\&=\sum\limits_{i=k}^{len}(len-i+1)\binom{i+k-3}{2k-3}\\&=\sum\limits_{i=0}^{len-k}(len-i-k+1)\binom{i+2k-3}{2k-3}\\&=(len-k+1)\sum\limits_{i=0}^{len-k}\binom{i+2k-3}{2k-3}-\sum\limits_{i=0}^{len-k}i\binom{i+2k-3}{2k-3}\\&=(len-k+1)\binom{len+k-2}{2k-2}-(2k-2)\sum\limits_{i=0}^{len-k}\binom{i+2k-3}{2k-2}\\&=(len-k+1)\binom{len+k-2}{2k-2}-(2k-2)\binom{len+k-2}{2k-1}\\&=(len-k+1)\frac{(len+k-2)!}{(2k-2)!(len-k)!}-(2k-2)\frac{(len+k-2)!}{(2k-1)!(len-k-1)!}\\&=(len-k+1)(2k-1)\frac{(len+k-2)!}{(2k-1)!(len-k)!}-(2k-2)(len-k)\frac{(len+k-2)!}{(2k-1)!(len-k)!}\\&=\frac{(len+k-2)!}{(2k-1)!(len-k)!}(len+k-1)\\&=\binom{len+k-1}{2k-1}\end{aligned}\)

If \ (k=0 \), the third one can be output directly
Otherwise, these people divide the sequence into intervals
Considering the calculation of the generating function of the answer, the coefficients in an interval are directly given by the above combination formula. When merging the intervals, only the generating functions of the two intervals need to be convoluted, so divide and conquer multiplication can be used
Remember a new way to write divide and conquer multiplication. First get all the functions into deque, then take out the two functions at the head of the team each time, and put their products at the end of the team
Time complexity \ (O(n\log^2n) \)

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mod=998244353;
int read()
{
	int ret=0;char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')ret=((ll)ret*10%mod+c-48)%mod,c=getchar();
	return ret;
}
int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=(ll)a*a%mod)if(b&1)ret=(ll)ret*a%mod;return ret;}
const int maxn=2e5+5;
int n,m,k;
int a[maxn];
int R[1<<21],W[1<<21];
struct poly
{
	vector<int>v;
	int& operator [](int i){return v[i];}
	void ntt(int L,int typ)
	{
		int n=pow(2,L);
		for(int i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
		W[0]=1;W[1]=qpow(3,(mod-1)/n);if(typ==-1)W[1]=qpow(W[1],mod-2);
		for(int i=2;i<n;i++)W[i]=(ll)W[i-1]*W[1]%mod;
		if(v.size()<n)v.resize(n,0);
		for(int i=0;i<n;i++)if(R[i]>i)swap(v[i],v[R[i]]);
		for(int t=n>>1,d=1;d<n;d<<=1,t>>=1)
			for(int i=0;i<n;i+=(d<<1))
				for(int j=0;j<d;j++)
				{
					int tmp=(ll)W[t*j]*v[i+j+d]%mod;
					v[i+j+d]=(v[i+j]-tmp+mod)%mod;
					v[i+j]=(v[i+j]+tmp)%mod;
				}
		if(typ==-1){int inv=qpow(n,mod-2);for(int i=0;i<n;i++)v[i]=(ll)v[i]*inv%mod;}
	}
	poly operator *(poly &x)
	{
		poly ret;
		int ori=v.size(),xori=x.v.size();
		int L=ceil(log2(v.size()+x.v.size()-1)),n=pow(2,L);
		ntt(L,1);x.ntt(L,1);
		ret.v.resize(n);
		for(int i=0;i<n;i++)ret[i]=(ll)v[i]*x[i]%mod;
		ret.ntt(L,-1);ntt(L,-1);x.ntt(L,-1);
		while(v.size()>1&&v.back()==0)v.pop_back();
		while(x.v.size()>1&&x.v.back()==0)x.v.pop_back();
		while(ret.v.size()>1&&ret.v.back()==0)ret.v.pop_back();
		return ret;
	}
};
deque<poly>q;
int fac[maxn<<1],inv[maxn<<1];
void prework()
{
	fac[0]=1;for(int i=1;i<=2*n+1;i++)fac[i]=(ll)fac[i-1]*i%mod;
	inv[0]=inv[1]=1;for(int i=2;i<=2*n+1;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
	for(int i=2;i<=2*n+1;i++)inv[i]=(ll)inv[i-1]*inv[i]%mod;
}
int C(int n,int m){return (ll)fac[n]*inv[n-m]%mod*inv[m]%mod;}
int main()
{
	n=read();m=read();k=read();
	generate_n(a+1,k,read);
	prework();
	if(!k){printf("%lld\n",(ll)C(n+m-1,2*m-1)*fac[m]%mod);return 0;}
	if(a[1]>1)
	{
		poly now;now.v.resize(a[1]);
		for(int i=0;i<=a[1]-1;i++)now[i]=C(a[1]-1+i,2*i);
		q.push_back(now);
	}
	if(a[k]<n)
	{
		poly now;now.v.resize(n-a[k]+1);
		for(int i=0;i<=n-a[k];i++)now[i]=C(n-a[k]+i,2*i);
		q.push_back(now);
	}
	for(int i=1;i<k;i++)
	{
		int len=a[i+1]-a[i]-1;
		poly now;now.v.resize(len+1);
		for(int j=0;j<=len;j++)now[j]=C(len+j+1,2*j+1);
		q.push_back(now);
	}
	while(q.size()>=2)
	{
		q.push_back(q[0]*q[1]);
		q.pop_front();q.pop_front();
	}
	printf("%lld\n",(ll)q[0][m-k]*fac[m-k]%mod);
	return 0;
}