洛谷P3560 [POI2013] LAN-Colorful Chain 题解

题目链接：P3560 [POI2013] LAN-Colorful Chain

题意：

小 Bajtuś 非常喜欢玩彩色链条。他已经收集了相当多的链条，不过有些他喜欢的比其他的更多。每条链条由若干个彩色链环组成。Bajtazar 注意到 Bajtuś 对美学有非常精确的偏好。具体来说，Bajtuś 认为一段连续的链条是漂亮的，如果它恰好包含 \(l_1\) 个颜色为 \(c_1\) 的链环，\(l_2\) 个颜色为 \(c_2\) 的链环，......，\(l_m\) 个颜色为 \(c_m\) 的链环，并且不包含任何其他颜色的链环。

链条的吸引力等于漂亮的（连续）片段的数量。Bajtazar 通过试错法找出了 \(l_1, \cdots , l_m\) 和 \(c_1, \cdots , c_m\) 的值。

现在他想买一条新的链条，并请求你编写一个程序来帮助他购买。

省流：对于字符串 \(a\) ，找到漂亮的子串的总数。

输入格式：

标准输入的第一行包含两个整数 \(n\) 和 \(m\) （ \(1 \le m \le n \le 10^6\) ），用一个空格隔开。

它们分别表示链条的长度和漂亮片段的描述长度。

第二行包含 \(m\) 个整数 \(l_1, \cdots, l_m\) （ \(1 \le l_i \le n\) ），用单个空格分隔。

第三行包含 \(m\) 个整数 \(c_1, \cdots, c_m\)（ \(1 \le c_i \le n\) ，对于 \(i \ne j,~c_i ≠ c_j\) ），用单个空格分隔。

序列 \(l_1, \cdots l_m\) 和 \(c_1, \cdots c_m\) 描述了漂亮片段的定义——它必须恰好包含 \(l_i\) 个颜色为 \(c_i\) 的链环。

第四行包含 \(n\) 个整数 \(a_1, \cdots, a_n\) （ \(1 \le a_i \le n\) ），用单个空格分隔，表示链条中每个链环的颜色。

输出格式：

在标准输出的第一行，你的程序应该输出一个整数——链条中漂亮的连续片段的数量。

听说本题是和哈希（Sum hash）的模板题？我怎么觉得 P8819 比这个更模板

正解就是类似于前缀和，它合法片段都是定长的，随便搞搞就过了吧（

来讲哈希。考虑给每个颜色赋一个随机权值 \(w_i\) ，一个子串的哈希值定义如下 \[ \sum_i l_i\times w_i \] 一个子串的哈希值就和漂亮串的哈希值相等是这个串合法的必要不充分条件，即 \[ \sum_i l_i\times w_i=\text{Good} \] 如果我们把 \(l_i\) 看作未知数，其他看作常数，那么 \((l_1,l_2,\cdots,l_m)\) 显然是原方程的一组解

然而，显然存在一些情况，有其他的合法解。但由于 \(w_i\) 是随机的，没法构造数据去卡这种做法。

如果觉得跑一遍不太靠谱，可以多跑几遍，比如我跑了三遍，取答案的中位数（其实还是随机不是么）

时间复杂度 \(\mathcal{O}(kn)\) ，\(k\) 是哈希的次数

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e6 + 15))
#define K 3

int n, m, res[K], now[K], good[K], a[N], w[K][N], num[N], col[N];
mt19937 rd(time(0)); unordered_map<int,int> mp;
void work(int k)
{
    mp.clear(); mp[0] = 1;
    for(int i = 1; i <= n; i++) w[k][i] = rd();
    for(int i = 1; i <= m; i++)
        good[k] += num[i] * w[k][col[i]];
    for(int i = 1; i <= n; i++)
    {
        now[k] += w[k][a[i]];
        res[k] += mp[now[k] - good[k]]; ++mp[now[k]];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= m; i++) cin >> num[i];
    for(int i = 1; i <= m; i++) cin >> col[i];
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int k = 0; k < K; k++) work(k);
    sort(res, res + K); cout << res[1] << '\n';
    return 0;
}