专栏文章

题解：CF1188E Problem from Red Panda

iincludeCPP
CF1188E题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqo713v
此快照首次捕获于
2025/12/04 08:00
3 个月前
此快照最后确认于
2025/12/04 08:00
3 个月前
查看原文
题意：每次操作所有的颜色 −1-1，选择一种 +k+k。不能出现负数。求最后的颜色序列数。
设最终颜色 ii 操作了 xix_i 次，令 sum=∑xisum=\sum x_i。
不难发现最终每个颜色的个数为 ai+xik−suma_i+x_ik-sum。
注意到上式 xix_i 同时变化式子是不变的。
因为颜色序列在操作过程中每个元素均不能为负，推个式子：
∵ai+xik−sum≥0\because a_i+x_ik-sum\ge 0\\ ∴xi≥⌈max⁡{sum−ai,0}k⌉\therefore x_i\ge \lceil \frac{\max\{sum-a_i,0\}}{k}\rceil \\ ∴sum=∑xi≥∑⌈max⁡{sum−ai,0}k⌉\therefore sum=\sum x_i\ge \sum \lceil \frac{\max\{sum-a_i,0\}}{k}\rceil
注意到式子与 xix_i 无关，且 ∀m∈[0,sum] \forall m \in [0,sum] 也满足这个式子。
不难发现 sum>amax⁡→xmin⁡>0sum>a_{\max} \to x_{\min}>0，因此我们枚举 sum∈[0,amax⁡]sum \in [0,a_{\max}] 即可。
那么我们先把 aa 从小到大排序，发现随着 sumsum 的增加，需操作位置分界线 pp 单调右移，双指针维护即可。显然下界之和可以用桶维护，令其为 ww，则插板法简单容斥即得方案数：
(s+k−w−1k−1)−(s+p−w−1k−1)\binom{s + k - w - 1}{k - 1} - \binom{s + p - w - 1}{k - 1} CPP
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e6+5,mod=998244353;
typedef long long ll;
ll fac[N],inv[N];
ll k,a[N],f[N];
ll fpow(ll a,ll b){
	ll res=1ll;
	while(b>=1ll){
		if(b&1ll){
			res=(res*a)%mod;
		}
		a=(a*a)%mod;
		b>>=1;
	}
	return res%mod;
}
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;i++){
		fac[i]=fac[i-1]*i%mod;
	}
	inv[n]=fpow(fac[n],mod-2);
	for(int i=n;i>=1;i--){
		inv[i-1]=inv[i]*i%mod;
	}
	return ;
}
ll C(int n,int m){
	if(n<0||m<0)return 0;
	return fac[n]*inv[n-m]%mod*inv[m]%mod;
}
ll calc(ll x,ll y){
	return C(x+y-1,x);
}
int main(){
	init(2000001);
	ll n=0;
	cin>>k;
	for(int i=1;i<=k;i++){
		scanf("%lld",&a[i]);
		n+=a[i];
	}
	sort(a+1,a+k+1);
	ll res=0,p=1,ans=0;
	for(int i=0;i<=a[k];i++){
		while(a[p]<i){
			f[a[p]%k]++;
			p++;
		}
		res+=f[(i+k-1)%k];
		if(i<res)break;
		ans=(ans+(calc(i-res,k)-calc(i-res+p-k-1,k))%mod+mod)%mod;
	}
	cout<<(ans+mod)%mod;
	return 0;
}

评论

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

正在加载评论...