题解：AT_arc190_b [ARC190B] L Partition
FS_NEO
·
·
题解
设 $f_k=\sum_{i=a-k}^{a-1} \binom{n-k}{i}$，由于想要凑出递推式，我们：
$$
\begin{align*} 2 f_{k+1} &=2 \sum_{i=a-k-1}^{a-1} \binom{n-k-1}{i} \\
& =\sum_{i=a-k}^{a-1} \binom{n-k-1}{i} + \sum_{i=a-k}^{a-1} \binom{n-k-1}{i-1} + \binom{n-k-1}{a-k-1} +\binom{n-k-1}{a-1} \\
&=\sum_{i=a-k}^{a-1} \binom{n-k}{i} + \binom{n-k-1}{a-k-1} +\binom{n-k-1}{a-1} \\
&= f_{k} + \binom{n-k-1}{a-k-1} +\binom{n-k-1}{a-1}
\end{align*}
$$
于是我们能线性预处理出 $f$ 数组，对于 $b$ 同理。详见代码。
```cpp
/*
2025.11.8
* Happy Zenith Noises *
*/
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define RG register
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>PP;
typedef unordered_map<int,int>ump;
const int MAXN=10000005,mod=998244353,inf=0x3f3f3f3f;
int A[MAXN],B[MAXN],T[MAXN],S[MAXN];
int n,m,a,b,k,inv2;
int fa[MAXN],fb[MAXN];
inline int gt(int x){return (x%mod+mod)%mod;}
int C(int x,int y){
if(x<0||x>y)return 0;
return A[y]*B[x]%mod*B[y-x]%mod;
}
void solve(){
cin>>k;
if(k==1){cout<<C(a-1,n-1)*C(b-1,n-1)%mod<<'\n';return ;}
int ans=0;
if(b+k-1<=n)ans=(ans+C(b-1,n-k)*fa[k])%mod;
if(a+k-1<=n)ans=(ans+C(a-1,n-k)*fb[k])%mod;
if(a+k-1<=n&&b+k-1<=n)ans=(ans-C(a-1,n-k)*C(b-1,n-k))%mod;
if(b+k-1<=n)ans=(ans+C(b-1,n-k)*fa[k])%mod;
if(a-k+1>=1)ans=(ans+C(a-k,n-k)*fb[k])%mod;
if(a-k+1>=1&&b+k-1<=n)ans=(ans-C(a-k,n-k)*C(b-1,n-k))%mod;
if(b-k+1>=1)ans=(ans+C(b-k,n-k)*fa[k])%mod;
if(a-k+1>=1)ans=(ans+C(a-k,n-k)*fb[k])%mod;
if(a-k+1>=1&&b-k+1>=1)ans=(ans-C(a-k,n-k)*C(b-k,n-k))%mod;
if(b-k+1>=1)ans=(ans+C(b-k,n-k)*fa[k])%mod;
if(a+k-1<=n)ans=(ans+C(a-1,n-k)*fb[k])%mod;
if(a+k-1<=n&&b-k+1>=1)ans=(ans-C(a-1,n-k)*C(b-k,n-k))%mod;
cout<<gt(ans*S[k-1])<<"\n";
}
int pw(int base,int t){
int ans=1;
while(t){
if(t&1)ans=ans*base%mod;
base=base*base%mod,t>>=1;
}
return ans;
}
signed main(){
ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
A[0]=B[0]=S[0]=1,S[1]=1;inv2=pw(2,mod-2);
for(int i=1;i<MAXN-1;i++)A[i]=A[i-1]*i%mod,S[i+1]=S[i]*4%mod;
for(int i=MAXN-2,t=pw(A[MAXN-2],mod-2);i>=1;i--)B[i]=t,t=t*i%mod;
cin>>n>>a>>b>>m;
fa[1]=C(a-1,n-1);fb[1]=C(b-1,n-1);
for(int i=2;i<=n;i++){
fa[i]=(fa[i-1]+C(a-i,n-i)+C(a-1,n-i))%mod*inv2%mod;
fb[i]=(fb[i-1]+C(b-i,n-i)+C(b-1,n-i))%mod*inv2%mod;
}
while(m--)solve();
return 0;
}
```