CF1738E

标签：CF1738E big ll 阶乘 using sum DP

[[inverse element]]
link: E - Balance Addicts
虽然说CF上有DP标签，但是不能算完全意义上的DP，可以不通过DP来理解

就是在到 \(i\) 的前缀和 和 到 \(j\) 的后缀和相同时做处理

如果没有0就是每次找到直接ans*=2
现在有0就复杂一点，两边能分出的区间数必须是相同的，所以枚举分成多少区间，然后乘上个组合数，实际上没有0可以看成有0个0，可以套同一个公式
每次的变化就是乘上\(\sum_{i=0}^{min\{a,b\}}\big(_i^a\big)\big(_i^b\big)\)
这里的 \(a\) \(b\) 表示两侧 \(0\) 的个数+1

一开始的两侧需要特殊处理，因为边界是必须要取的

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=100005,p=998244353;
ll n,T,a[N],sa[N],sb[N],mk[N],ans,ca,cb;
ll fac[N]={1,1},inv[N]={0,1},ivf[N]={1,1},sum,bo,l,r;
ll calc(ll a,ll b){
	ll mi=min(a,b),ret=0;
	for(int i=0;i<=mi;i++)(ret+=fac[a]*ivf[i]%p*ivf[a-i]%p*fac[b]%p*ivf[b-i]%p*ivf[i]%p)%=p;
	return ret;
}
int main(){
	int i,j;
	for(i=2;i<N;i++)inv[i]=inv[p%i]*(p-p/i)%p;
	for(i=2;i<N;i++)fac[i]=fac[i-1]*i%p,ivf[i]=ivf[i-1]*inv[i]%p;
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&n);ans=1;
		for(i=1;i<=n;i++)scanf("%lld",a+i);
		if(n==1){
			printf("1\n");
			continue;
		}
		sa[0]=sb[n+1]=0;
		for(i=1;i<=n;i++)sa[i]=a[i]+sa[i-1];
		for(i=n;i;i--)sb[i]=a[i]+sb[i+1];
		sum=sb[1],bo=1;
		if(!sum){
			ans=1;
			for(int i=1;i<n;i++)ans=ans*2%p;
			printf("%lld\n",ans);
			continue;
		}
		l=1,r=n;
		for(l=1;!a[l];l++);for(r=n;!a[r];r--);
		ans=calc(l-1,n-r);
		while(l<r){
			if(sa[l]<sb[r])l++;
			else if(sa[l]>sb[r])r--;
			else{
				i=l,j=r;
				for(l++;l<r&&!a[l];l++);
				if(l<r){
					for(r--;l<r&&!a[r];r--);
					(ans*=calc(l-i,j-r))%=p;
				}else{
					for(;i<j;i++)ans=ans*2%p;
					break;
				}
			}
		}
		printf("%lld\n",ans);
	}
}

这里有用到线性求逆元，因为要O(1)求组合数，要预处理阶乘和阶乘的逆元

标签：CF1738E,big,ll,阶乘,using,sum,DP
From： https://www.cnblogs.com/-WD-/p/16973141.html