专栏文章

题解：AT_arc190_b [ARC190B] L Partition

FFS_NEO
AT_arc190_b题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min8wmhz
此快照首次捕获于
2025/12/01 22:29
3 个月前
此快照最后确认于
2025/12/01 22:29
3 个月前
查看原文
O(n2)O(n^2) 做法是简单的，难点在于优化。
设 fk=∑i=a−ka−1(n−ki)f_k=\sum_{i=a-k}^{a-1} \binom{n-k}{i}，由于想要凑出递推式，我们：
2fk+1=2∑i=a−k−1a−1(n−k−1i)=∑i=a−ka−1(n−k−1i)+∑i=a−ka−1(n−k−1i−1)+(n−k−1a−k−1)+(n−k−1a−1)=∑i=a−ka−1(n−ki)+(n−k−1a−k−1)+(n−k−1a−1)=fk+(n−k−1a−k−1)+(n−k−1a−1) \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*}
于是我们能线性预处理出 ff 数组，对于 bb 同理。详见代码。
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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...