专栏文章

P14364 Sol || 别样的容斥大战

CCarroT1212菜萝卜
P14364题解参与者 9已保存评论 8

文章操作

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

当前评论
8 条
当前快照
1 份
快照标识符
@minez73j
此快照首次捕获于
2025/12/02 01:19
3 个月前
此快照最后确认于
2025/12/02 01:19
3 个月前
查看原文
一个很丝滑的容斥做法！
设 ∑si=k\sum s_i=k。首先我们把题意转换为，要从 nn 个人中选出 kk 个人（si=1s_i=1 的位置），剩下的人随便排。
对于第 ii 个人，若他的忍耐值为 viv_{i}（原序列中的某个 cic_i），设前 i−1i-1 个人走了 tit_i 个，那么这个人会在 vi≤wi+tiv_i\le w_i+t_i 时走掉。wiw_i 是这个 si=1s_i=1 在原串中前面 00 的个数，表示强制走掉的人。
以下的“人”和“走”都是针对这 kk 个人而言的。主要处理瓶颈在于，后面一个人走不走取决于前面的状态。
m=1m=1 的做法
我们反过来计算 kk 个人全部走掉的方案数。这里其实有一个细想起来很巧妙的结构：
因为要计算的方案只有全部走掉这一种，那么对于所有符合情况的方案，一定有 ti=i−1t_i=i-1。
反过来，如果在这样的 tit_i 下，我们确实让每个 viv_i 都 ≤wi+ti\le w_i+t_i，那这就是一个所有人都走了的方案。
换句话说，因为走人情况是固定的，所以符合情况的排列方案的 tit_i 也是固定的，我们只需要在这个 tit_i 下计算符合情况的方案数即可。
在这里就是计算所有 vi≤wi+i−1v_i\le w_i+i-1 的选人方案数。
由于 wiw_i 是单调不降的，方案数为 res=∏i=1k(sumwi+i−1−(i−1))res=\prod\limits_{i=1}^k (sum_{w_i+i-1}-(i-1))。最终答案就是 n!−(n−k)!⋅resn!-(n-k)!\cdot res。
受上述做法启发，我们尝试去分别计算每个走人情况被多少排列方案取到。这样 tit_i 可以当做定值，会好处理得多。
枚举走人情况，容易根据这个情况求出此时的 tit_i。还是一样，去按照这个 tit_i 计算每个人都按照这个情况走了/没走的方案数。
具体来说，对于一个 ii，如果我们指定他走，那么 viv_i 就要 ≤wi+ti\le w_i+t_i。否则需要 >wi+ti>w_i+t_i。
出现了另一个方向的限制，导致我们并不好像 m=1m=1 那样直接计算。考虑容斥。
  • 对于这种两个相反方向的限制，我们可以通过对其中一个方向容斥，使得这些方向的限制，一部分变得反向，另一部分没有限制。那就变成了很多个同向限制问题，可能会更好处理。类似思想的题目有 AGC036F P5405 等。
这题也是同理的。我们容斥有一部分 vi>wi+tiv_i>w_i+t_i 的限制没有满足，也就是强制这些 vi≤wi+tiv_i\le w_i+t_i。剩下没被容斥到的 vi>wi+tiv_i>w_i+t_i 限制就直接消失，可以和那 n−kn-k 个人一起随便排。
删去容斥之后没有限制的位，现在相当于有 k′k' 个人，每个人都要 vi≤wi+tiv_i\le w_i+t_i，由于 wi+tiw_i+t_i 也单调不降，就变成了一个和上面 m=1m=1 几乎一模一样的问题。很容易计算。
O(3n)O(3^n) 暴力容斥代码CPP
for (ll s=0;s<1ll<<k;s++) if (__builtin_popcount(s)>=m) {
	ll res=0;
	for (ll t=s;;t=(t-1)&s) {
		ll rw=1,x=0,y=0;
		for (ll i=1;i<=k;i++) {
			if (s>>i-1&1^1) (rw*=max(sum[w[i]+x]-x-y,0ll))%=P,x++;
			else if (t>>i-1&1) (rw*=max(sum[w[i]+x]-x-y,0ll))%=P,y++;
		}
		(res+=(y&1?P-1:1)*rw%P*fac[n-x-y])%=P; 
		if (!t) break;
	}
	(ans+=res)%=P;
}
可以发现这些容斥贡献都可以摊到 DP 过程里计数。设 dpi,x,ydp_{i,x,y} 表示前 ii 个数，我们指定的走人方案现在走了 xx 个人，并且容斥反向了 yy 个指定没走的人的限制，当前的方案贡献之和。直接转移 O(n3)O(n^3)。转移非常简单。
正解代码CPP
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std; bool MEM;
using ll=long long; using ld=long double;
using pii=pair<int,int>; using pll=pair<ll,ll>;
const int I=1e9;
const ll J=1e18,N=507,P=998244353;
ll fac[N];
ll n,m,c[N],sum[N],k,w[N],ans; int dp[N][N][N];
char s[N];
void mian() {
	fac[0]=1; for (ll i=1;i<N;i++) fac[i]=fac[i-1]*i%P;
	scanf("%lld%lld%s",&n,&m,s+1);
	for (ll i=1;i<=n;i++) if (s[i]-'0'==1) k++,w[k]=i-k;
	if (!k) return cout<<"0",void();
	for (ll i=1;i<=n;i++) scanf("%lld",&c[i]),sum[c[i]]++;
	for (ll i=1;i<=n;i++) sum[i]+=sum[i-1];
	dp[0][0][0]=1;
	for (ll i=1,o=1;i<=k;i++) for (ll x=0;x<i;x++) for (ll y=0;x+y<i;y++) {
		(dp[i][x+1][y]+=dp[i-1][x][y]*max(sum[w[i]+x]-x-y,0ll)%P)%=P; // 指定第 i 个人走 
		(dp[i][x][y+1]+=dp[i-1][x][y]*max(sum[w[i]+x]-x-y,0ll)%P)%=P; // 指定他没走，容斥它 
		(dp[i][x][y]+=dp[i-1][x][y])%=P; // 指定他没走，不容斥它 
	}
	for (ll x=0;x<=k-m;x++) for (ll y=0;x+y<=k;y++)
		(ans+=(y&1?P-1:1)*dp[k][x][y]%P*fac[n-x-y])%=P;
	cout<<ans;
}
bool ORY; int main() {
//	while (1)
//	int t; for (scanf("%d",&t);t--;)
	mian();
	cerr<<"\n"<<abs(&MEM-&ORY)/1048576<<"MB";
	return 0;
}
我赛时干啥了
贡献延迟计算做法没试出来怎么转移，很悲伤。
然后我对着 A 性质的错误转化想了总共至少半小时，才发现转化是错的，并得到了一个没有可推广性的 A 性质做法。
感觉时间不够做出这题了，尝试再拼几个好分，接着想 m=1m=1。
这时我才发现我完全没尝试过直接计数一个走人情况的方案数。然后我很快意识到了可以容斥。
但是我脑子一昏想错了一个细节：我的 tit_i 是根据容斥之后的走人状态求的。
这是不应该的。因为我们原本研究出的 vi≤ti+wi/vi>ti+wiv_i\le t_i+w_i/v_i>t_i+w_i 是一个充要得不能再充要的条件，对着它去刻画本来就能得到对的结果，而你画蛇添足去根据容斥时的状态加这么个变化 tit_i 的细节，只会导致整个结果都是混乱的。
也就是，你尝试容斥的不应该是“至少有哪些人走了”（就算 tit_i 根据容斥后状态求，算出来也不是这个东西），而是只是单纯的符不符合这些限制。
这个时候时间实在太晚了，我还没反应过来，不敢再修了，拼好分去了。

评论

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

正在加载评论...