专栏文章

题解：AT_arc171_d [ARC171D] Rolling Hash

lliborui0000
AT_arc171_d题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miod7e1s
此快照首次捕获于
2025/12/02 17:17
3 个月前
此快照最后确认于
2025/12/02 17:17
3 个月前
查看原文

题目大意

给定整数 PP，BB 满足 PP 是质数，1≤B≤P−11 ≤ B ≤ P − 1。对于序列 X=(x1,x2,⋅⋅⋅,xn)X = (x_{1}, x_{2}, · · · , x_{n})，定义 hash(X)hash(X) 的值为

hash(X)≡∑i=1nxiBn−i(modP)hash(X) \equiv \sum_{i = 1}^{n} x_{i} B^{n - i}\pmod P

给定 MM 对整数(Li,RiL_{i}, R_{i})(1≤i≤M1 ≤ i ≤ M)，请问是否存在长度为 NN 的序列 A=(a1,a2,⋅⋅⋅,an)A = (a_{1}, a_{2}, · · · , a_{n}) 满足：对每一个 ii(1≤i≤M1≤ i ≤ M)，都有

hash((ALi,ALi+1,…,ARi))=0hash((A_{L_{i} } ,A_{L_{i} + 1 },\dots , A_{R_{i} })) = 0。

思路

如果学过字符串哈希，可以很快写出区间哈希值：

Hashl,r=Hash1,r−Hash1,l−1×Br−l+1=(Hashl,n−Hashr+1,n)×Br−nHash_{l, r} = Hash_{1, r} − Hash_{1, l - 1}×B^{r - l + 1} = (Hash_{l, n} − Hash_{r + 1,n}) × B^{r - n}

中间的式子显然不好做，因为 Br−l+1B^{r - l + 1} 不容易维护。但是后面的形式很容易啊，因为 Br−nB^{r - n} 必不可能为 00，哈希值为 00 相当于Hashl,n=Hashr+1,nHash_{l, n} = Hash_{r +1,n}。
在 modPmodP 意义下，哈希值的下一位是几都可以构造出来，因为下一位可以取遍 0∼P−10 ∼ P − 1 的每个数。所以题意转化成要给 1∼n1 ∼ n 每个点赋 0∼P−10 ∼ P − 1 的权值，n+1n + 1 权值为 00，然后给你 mm 条边，你要保证边连接的两个点权值不同。
  • 当 P>nP > n 时，颜色数不少于点数，一定有解。
  • 当 P≤nP ≤ n 时，等价于图染色，不能多项式。
设 fsf_{s} 表示将点 SS 中点的导出子图染色，最少用几种颜色。每次开一个新颜色，染成新颜色的点得是一个独立集 TT，则：

fS=min(T⊆SfS−T+1)f_{S} = min(_{T\subseteq S}f_{S - T} + 1 )

其中 TT 为独立集。
如果 fU≤Pf_{U} ≤ P 则存在符合条件的序列，其中 UU 为全部节点集。复杂度是枚举子集：O(3n)O(3^{n} )。（不会枚举子集的出门右转）

代码

CPP
#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 17;

int p, b, n, m;
int g[1 << N], G[N][N], f[1 << N];

signed main(){
	cin >> p >> b >> n >> m;
	for (int i = 1; i <= m; i++){
		int l, r;
		cin >> l >> r;
		G[l - 1][r] = 1;
		G[r][l - 1] = 1;
	}
	if (p > n){
		cout << "Yes" << "\n";
		return 0;
	}
	const int U = (1 << (n + 1)) - 1;
	for (int i = 0; i <= U; i++){
		g[i] = 1;
		for (int j = 0; j <= n; j++){
			if ((i >> j) & 1){
				for (int k = j + 1; k <= n; k++){
					if ((i >> k) & 1){
						if (G[j][k]) g[i] = 0;
					}
				}
			}
		}
	}
	memset(f, 0x3f, sizeof f);
	f[0] = 0;
	for (int i = 1; i <= U; i++){
		for (int j = i; j; j = (j - 1) & i){
			if (g[j]){
				f[i] = min(f[i], f[i ^ j] + 1);
			}
		}
	}
	if (f[U] <= p) cout << "Yes" << "\n";
	else cout << "No" << "\n";
	return 0;
}

评论

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

正在加载评论...