2023NOIP A层联测18 划分

题目大意

对于一个长度为$n$的$01$字符串$S$，请求出将其分为至少$k$段，将每段看成二进制数求和后的最大值以及取到这个最大值的划分方案的数量。

输出最大值模$998244353$后的值和划分方案的数量模$998244353$后的值。

$1\le n,k\le 2\times 10^6$

题解

如果前$k$位没有$1$，则最优解一定是第一个$1$之前所有间隔中选$k-1$个及以上的间隔（因为把最后一段形成的二进制数从中间分开一定会减小），可以用组合数来计算。如果一个$1$都没有，则最优解就是$n-1$个间隔中选$k-1$个及以上的间隔。

如果不满足上面的条件，则最优解一定是选出一段长度为$n-k+1$子串，剩下的每一个数单独分一段。我们考虑比较两种划分方案的大小。

设第一种划分方案的$n-k+1$的串看成的二进制数为$v_1$，其余$k-1$段中$1$的个数为$t_1$，第二种划分方案的$n-k+1$的串看成的二进制数为$v_2$，其余$k-1$段中$1$的个数为$t_2$。当$v_1>v_2$时

• 如果$v_1$和$v_2$的前$n-k$位相同，而$v_1$的最后一位为$1$，$v_2$的最后一位为$0$，则$t_1+1=t_2$，两种划分方案的结果是相同的
• 如果$v_1$和$v_2$的前$n-k$位存在不同，则设第一个不同的位为$t$
  • 如果$t_1\ge t_2$，则显然第一种方案更优
  • 如果$t_1<t_2$，则我们将$S$中的每个$1$减去对答案的贡献$1$，两种划分方案的大小关系不变。此时其余$k-1$段中的$1$都不算贡献，最大段中每一个为$1$的位$i$的贡献为$2^i-1$，那么两种方案中前$t-1$个位置的贡献相同，第一种方案中第$t$位的贡献为$2^t-1$，而第二种划分方案中第$t$位为$0$，之后的位之和小于等于$2^t-1$，因为每个$1$的贡献都被减去了$1$，所以之后的位的贡献之和小于$2^t-1$，得第一种方案更优

由此可得，以$1,2,\dots ,k$开头，长度为$n-k+1$的串中，划分出的串为字典序最大的串的结果最优。如果字典序最大的串的最后一位为$1$，前面$n-k$位与其相同，最后一位为$0$的串也是最优的。

那我们怎么求字典序最大的串呢？可以用二分哈希。从$1$到$k$枚举$i$，设$l$为以$1$到$i-1$为起点的串中字典序最大的串的起点，那么对于当前的$i$，我们要比较$l$开头的串和$i$开头的串的字典序的大小。那么，我们可以二分两个串最长的公共前缀，假设公共前缀为$1$到$t$，则$t+1$即为两个串中第一个不同的位置，比较这个位置的大小即可知道两个串的大小关系。用哈希可以$O(1)$判断两个字符串是否相同，所以处理一个$i$的时间复杂度是$O(\log n)$的。

求出字典序最大的串之后，判断这个串的最后一位是否为$1$。如果是的话，将$1$改为$0$，再判断以$1,2,\dots ,k$开头，长度为$n-k+1$的串中是否有与这个修改后的串相同的，这同样可以用哈希来$O(1)$比较。

最大值可以用字典序最大的串对应的二进制数加其余部分的$1$的个数来得到，方案数可以在比较大小和是否相同的时候得到，那么这道题就解决了。

注意要特判$n==k$的情况，此时最大值为$S$中$1$的个数，方案数为$1$。

注意代码中虽然使用了单哈希，但这样有一定可能将两个不同的串判断为相同的串（有可能，但可能性不大），所以最好使用双哈希。

时间复杂度为$O(n\log n)$。

code

#include
using namespace std;
const int N=2000000;
const long long mod=998244353;
int n,k,len,sum[N+5];
long long ans1,ans2,p[N+5],pw[N+5],jc[N+5],ny[N+5];
char s[N+5];
long long mi(long long t,long long v){
	if(!v) return 1;
	long long re=mi(t,v/2);
	re=re*re%mod;
	if(v&1) re=re*t%mod;
	return re;
}
void init(){
	jc[0]=1;pw[0]=1;
	for(int i=1;i<=N;i++){
		jc[i]=jc[i-1]*i%mod;pw[i]=pw[i-1]*2%mod;
	}
	ny[N]=mi(jc[N],mod-2);
	for(int i=N-1;i>=0;i--) ny[i]=ny[i+1]*(i+1)%mod;
}
long long C(int x,int y){
	return jc[x]*ny[y]%mod*ny[x-y]%mod;
}
long long hsh(int l,int r){
	return (p[r]-p[l-1]*pw[r-l+1]%mod+mod)%mod;
}
int gt(int i,int j){
	int l=1,r=len,mid;
	while(l<=r){
		mid=l+r>>1;
		if(hsh(i,i+mid-1)==hsh(j,j+mid-1)) l=mid+1;
		else r=mid-1;
	}
	return l-1;
}
int main()
{
//	freopen("divide.in","r",stdin);
//	freopen("divide.out","w",stdout);
	init();
	scanf("%d%d",&n,&k);len=n-k+1;
	scanf("%s",s+1);
	for(int i=1;i<=n;i++){
		sum[i]=sum[i-1]+s[i]-'0';
		p[i]=(p[i-1]*2+s[i]-'0')%mod;
	}
	if(!sum[n]){
		for(int i=k;i<=n;i++){
			ans2=(ans2+C(n-1,i-1))%mod;
		}
		printf("0 %lld",ans2);
		return 0;
	}
	if(k==n){
		printf("%lld 1",sum[n]);
		return 0;
	}
	if(sum[n-len+1]==0){
		int fst=1;
		while(s[fst]!='1') ++fst;
		ans1=hsh(fst,n);
		for(int i=k;i<=fst;i++){
			ans2=(ans2+C(fst-1,i-1))%mod;
		}
		printf("%lld %lld",ans1,ans2);
		return 0;
	}
	int l=1;ans2=1;
	for(int i=2;i+len-1<=n;i++){
		int vt=gt(l,i);
		if(vt==len) ++ans2;
		else if(s[l+vt]<s[i+vt]){
			l=i;ans2=1;
		}
	}
	if(s[l+len-1]=='1'){
		int hs=(hsh(l,l+len-1)-1)%mod;
		for(int i=1;i+len-1<=n;i++){
			if(hs==hsh(i,i+len-1)) ++ans2;
		}
	}
	ans1=hsh(l,l+len-1)+sum[l-1]+sum[n]-sum[l+len-1];
	printf("%lld %lld",ans1,ans2);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87