题解：AT_arc171_d [ARC171D] Rolling Hash

· · 题解

题目大意

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

hash(X) \equiv \sum_{i = 1}^{n} x_{i} B^{n - i}\pmod P

给定 M 对整数(L_{i}, R_{i})(1 ≤ i ≤ M)，请问是否存在长度为 N 的序列 A = (a_{1}, a_{2}, · · · , a_{n}) 满足：对每一个 i(1≤ i ≤ M)，都有

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

思路

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

Hash_{l, r} = Hash_{1, r} − Hash_{1, l - 1}×B^{r - l + 1} = (Hash_{l, n} − Hash_{r + 1,n}) × B^{r - n}

中间的式子显然不好做，因为 B^{r - l + 1} 不容易维护。但是后面的形式很容易啊，因为 B^{r - n} 必不可能为 0，哈希值为 0 相当于Hash_{l, n} = Hash_{r +1,n}。

在 modP 意义下，哈希值的下一位是几都可以构造出来，因为下一位可以取遍 0 ∼ P − 1 的每个数。所以题意转化成要给 1 ∼ n 每个点赋 0 ∼ P − 1 的权值，n + 1 权值为 0，然后给你 m 条边，你要保证边连接的两个点权值不同。

设 f_{s} 表示将点 S 中点的导出子图染色，最少用几种颜色。每次开一个新颜色，染成新颜色的点得是一个独立集 T，则：

f_{S} = min(_{T\subseteq S}f_{S - T} + 1 )

其中 T 为独立集。

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

代码

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