专栏文章

[题解] CF1750F Majority

MMonke_FClBrI
CF1750F题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqk5bdi
此快照首次捕获于
2025/12/04 06:07
3 个月前
此快照最后确认于
2025/12/04 06:07
3 个月前
查看原文
一种不容斥硬做的做法。
首先我们容易证明，一个合法的串一定可以通过若干次合并两段相邻的 11 来变成全 11 串。因为若某次合并了多段 11，假设合并的段形如 a1,b1,a2,b2,…,ana_1,b_1,a_2,b_2,\dots,a_n 的若干段（aa 为 11 段的长度，bb 为 00 段的长度），假设其中任意两个相邻的 11 段都无法合并，则有 a1−b1+a2,a2+b2+a3,⋯<0a_1-b_1+a_2,a_2+b_2+a_3,\dots<0，则有 0>(a1−b1+a2)+(a2−b2+a3)+⋯>a1−b1+a2−b2+⋯+an0>(a_1-b_1+a_2)+(a_2-b_2+a_3)+\dots>a_1-b_1+a_2-b_2+\dots+a_n，与“这些段可以直接合并”矛盾。同时一次合并不会使原来能合并的段合并不了，故可以每次只合并两个相邻的段。
接着考虑合并的过程。每个合法串可能有多种合并方法，我们钦定每次只能合并最靠左的可合并的相邻段，这样就不会算重了。考虑每个合法串的最后一次合并，一定是一个全 11 的前缀和一个全 11 的后缀合并起来。考虑对这个东西做 DP。
设 fi,jf_{i,j} 表示长度为 ii，且最后一次合并前前缀 11 的数量为 jj 的合法串数量（注意这里没有考虑初始时就是全 11 串的情况）。我们枚举全 11 后缀的长度 kk，可以发现 k∈[max⁡(1,⌈i2⌉−j),i−j−1]k\in[\max(1,\lceil\frac i 2\rceil-j),i-j-1]，设 L=max⁡(1,⌈i2⌉−j),R=i−j−1L=\max(1,\lceil\frac i 2\rceil-j),R=i-j-1。
先考虑后缀初始是全 11 的情况，可以发现由于前缀总是可以合并，所以总是合法的。
若后缀初始不全 11，考虑前缀全合并完后，在合并后缀时不能存在任何一个时刻使得前缀能和后缀的一段全 11 前缀合并，否则顺序就不对了。考虑后缀的全 11 前缀长度在后缀合并完之前何时取到最大（即最有可能被合并），发现正是后缀最后一次合并前。因此我再枚举后缀的“最后一次合并前前缀 11 的数量”ll，保证 j,lj,l 不能合并即可。于是可以得到转移：
fi,j=(1+∑l=1j−2fj,l)⋅(R−L+1+∑k=LR∑l=1i−2j−k−1fk,l)f_{i,j}=(1+\sum\limits_{l=1}^{j-2}f_{j,l})\cdot(R-L+1+\sum\limits_{k=L}^{R}\sum\limits_{l=1}^{i-2j-k-1}f_{k,l})
这样就是 O(n4)O(n^4) 的。然后可以前缀和优化，处理 gi,j=∑k=1i∑j=1i−kfk,l,si=1+∑j=1i−2fi,lg_{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)O(1) 转移，最后答案即为 sns_n。
复杂度 O(n2)O(n^2)。

代码

CPP
#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;
}
（逃

评论

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

正在加载评论...