P14364 Sol || 别样的容斥大战

· · 题解

一个很丝滑的容斥做法！

设 \sum s_i=k。首先我们把题意转换为，要从 n 个人中选出 k 个人（s_i=1 的位置），剩下的人随便排。

对于第 i 个人，若他的忍耐值为 v_{i}（原序列中的某个 c_i），设前 i-1 个人走了 t_i 个，那么这个人会在 v_i\le w_i+t_i 时走掉。w_i 是这个 s_i=1 在原串中前面 0 的个数，表示强制走掉的人。

以下的“人”和“走”都是针对这 k 个人而言的。主要处理瓶颈在于，后面一个人走不走取决于前面的状态。

:::info[m=1 的做法]{open} 我们反过来计算 k 个人全部走掉的方案数。这里其实有一个细想起来很巧妙的结构：

因为要计算的方案只有全部走掉这一种，那么对于所有符合情况的方案，一定有 t_i=i-1。

反过来，如果在这样的 t_i 下，我们确实让每个 v_i 都 \le w_i+t_i，那这就是一个所有人都走了的方案。

换句话说，因为走人情况是固定的，所以符合情况的排列方案的 t_i 也是固定的，我们只需要在这个 t_i 下计算符合情况的方案数即可。

在这里就是计算所有 v_i\le w_i+i-1 的选人方案数。

由于 w_i 是单调不降的，方案数为 res=\prod\limits_{i=1}^k (sum_{w_i+i-1}-(i-1))。最终答案就是 n!-(n-k)!\cdot res。 :::

受上述做法启发，我们尝试去分别计算每个走人情况被多少排列方案取到。这样 t_i 可以当做定值，会好处理得多。

枚举走人情况，容易根据这个情况求出此时的 t_i。还是一样，去按照这个 t_i 计算每个人都按照这个情况走了/没走的方案数。

具体来说，对于一个 i，如果我们指定他走，那么 v_i 就要 \le w_i+t_i。否则需要 >w_i+t_i。

出现了另一个方向的限制，导致我们并不好像 m=1 那样直接计算。考虑容斥。

这题也是同理的。我们容斥有一部分 v_i>w_i+t_i 的限制没有满足，也就是强制这些 v_i\le w_i+t_i。剩下没被容斥到的 v_i>w_i+t_i 限制就直接消失，可以和那 n-k 个人一起随便排。

删去容斥之后没有限制的位，现在相当于有 k' 个人，每个人都要 v_i\le w_i+t_i，由于 w_i+t_i 也单调不降，就变成了一个和上面 m=1 几乎一模一样的问题。很容易计算。

:::success[O(3^n) 暴力容斥代码]

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 过程里计数。设 dp_{i,x,y} 表示前 i 个数，我们指定的走人方案现在走了 x 个人，并且容斥反向了 y 个指定没走的人的限制，当前的方案贡献之和。直接转移 O(n^3)。转移非常简单。

:::success[正解代码]

#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;
}

:::

:::warning[我赛时干啥了] 贡献延迟计算做法没试出来怎么转移，很悲伤。

然后我对着 A 性质的错误转化想了总共至少半小时，才发现转化是错的，并得到了一个没有可推广性的 A 性质做法。

感觉时间不够做出这题了，尝试再拼几个好分，接着想 m=1。

这时我才发现我完全没尝试过直接计数一个走人情况的方案数。然后我很快意识到了可以容斥。

但是我脑子一昏想错了一个细节：我的 t_i 是根据容斥之后的走人状态求的。

这是不应该的。因为我们原本研究出的 v_i\le t_i+w_i/v_i>t_i+w_i 是一个充要得不能再充要的条件，对着它去刻画本来就能得到对的结果，而你画蛇添足去根据容斥时的状态加这么个变化 t_i 的细节，只会导致整个结果都是混乱的。

也就是，你尝试容斥的不应该是“至少有哪些人走了”（就算 t_i 根据容斥后状态求，算出来也不是这个东西），而是只是单纯的符不符合这些限制。

这个时候时间实在太晚了，我还没反应过来，不敢再修了，拼好分去了。 :::