[题解] CF1750F Majority

Monke_FClBrI · 2025-01-09 09:04:49 · 题解

一种不容斥硬做的做法。

首先我们容易证明，一个合法的串一定可以通过若干次合并两段相邻的 1 来变成全 1 串。因为若某次合并了多段 1，假设合并的段形如 a_1,b_1,a_2,b_2,\dots,a_n 的若干段（a 为 1 段的长度，b 为 0 段的长度），假设其中任意两个相邻的 1 段都无法合并，则有 a_1-b_1+a_2,a_2+b_2+a_3,\dots<0，则有 0>(a_1-b_1+a_2)+(a_2-b_2+a_3)+\dots>a_1-b_1+a_2-b_2+\dots+a_n，与“这些段可以直接合并”矛盾。同时一次合并不会使原来能合并的段合并不了，故可以每次只合并两个相邻的段。

接着考虑合并的过程。每个合法串可能有多种合并方法，我们钦定每次只能合并最靠左的可合并的相邻段，这样就不会算重了。考虑每个合法串的最后一次合并，一定是一个全 1 的前缀和一个全 1 的后缀合并起来。考虑对这个东西做 DP。

设 f_{i,j} 表示长度为 i，且最后一次合并前前缀 1 的数量为 j 的合法串数量（注意这里没有考虑初始时就是全 1 串的情况）。我们枚举全 1 后缀的长度 k，可以发现 k\in[\max(1,\lceil\frac i 2\rceil-j),i-j-1]，设 L=\max(1,\lceil\frac i 2\rceil-j),R=i-j-1。

先考虑后缀初始是全 1 的情况，可以发现由于前缀总是可以合并，所以总是合法的。

若后缀初始不全 1，考虑前缀全合并完后，在合并后缀时不能存在任何一个时刻使得前缀能和后缀的一段全 1 前缀合并，否则顺序就不对了。考虑后缀的全 1 前缀长度在后缀合并完之前何时取到最大（即最有可能被合并），发现正是后缀最后一次合并前。因此我再枚举后缀的“最后一次合并前前缀 1 的数量”l，保证 j,l 不能合并即可。于是可以得到转移：

这样就是 O(n^4) 的。然后可以前缀和优化，处理 g_{i,j}=\sum\limits_{k=1}^{i}\sum\limits_{j=1}^{i-k}f_{k,l},s_i=1+\sum\limits_{j=1}^{i-2}f_{i,l} 即可 O(1) 转移，最后答案即为 s_n。

复杂度 O(n^2)。

代码

#include<bits/stdc++.h>
#define pb push_back
#define SZ(x) (int)(x).size()
using namespace std;
const int N=5005;

// Modint ...

int n,mod;
MI f[N][N],g[N][N];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>mod;MI::setmod(mod);
    f[1][0]=f[2][0]=1;
    // f[i][0] <- s[i]
    for(int i=3;i<=n;i++){
        for(int j=1;j<=n;j++)g[i][j]=g[i-1][j];
        for(int j=1;j<i-1;j++){
            int L=max(1,(i+1)/2-j),R=i-j-1;
            f[i][j]=R-L+1;
            if(i-j*2-1>0)f[i][j]+=
                g[R][i-j*2-1]-g[L-1][i-j*2-1];
            f[i][j]*=f[j][0];
            f[i][j]+=f[i][j-1];
        }
        for(int j=i-1;j<=n;j++)f[i][j]=f[i][j-1];
        for(int j=1;j+i<=n;j++)g[i][j+i]+=f[i][j];
        f[i][0]=f[i][i-2]+1;
    }
    cout<<f[n][0]<<'\n';
    return 0;
}

（逃