P6273 [eJOI2017] 魔法 题解

· · 题解

提供一个小常数 O(nk\log n) 实现。

思路

根据题意，子串 S_{[l,r]} 是有魔法的，当且仅当 \forall k\in S,\sum\limits_{i=l}^r[S_i=k] 都相等。

维护前缀和 s_{x_k}=\sum\limits_{i=1}^x[S_i=k]，则 S_{[l,r]} 是有魔法的，当且仅当 \forall k\in S,s_{r_k}-s_{l-1_{k}} 都相等。

把 s_{r_a}-s_{l-1_a}=s_{r_b}-s_{l-1_b} 变形，得到 s_{r_a}-s_{r_b}=s_{l-1_a}-s_{l-1_b}，

任意选择一个 A\in S，则 S_{[l,r]} 是有魔法的，当且仅当 \forall k\in S,s_{r_k}-s_{r_A}=s_{l-1_k}-s_{l-1_A}。

维护 v_x=\{s_{x_k}-s_{x_A}|k\in S\}，则 S_{[l,r]} 是有魔法的，当且仅当 v_r=v_{l-1}。

考虑对于每个 r，求出满足 v_r=v_{l-1} 的 l 的个数。

正序枚举 r，维护一个 map，计算出 v_r 后，将答案加上 map 中 v_r 的个数，再将 v_r 加入 map。

代码

一些细节：

  1. 注意到 vector 自带比较运算符，所以可以开 map<vector<int>, int>。
  2. 注意到需要将字符作为 vector 的下标，所以需要离散化。
  3. 注意到 \forall x\in [1,n],v_x 只会用一次，所以可以动态更新 v_x。
  4. 注意到存在 l=1,l-1=0 的情况，所以需要事先将全 0 集合加入 map。
  5. 注意取模。注意答案开 long long。

感觉其他题解都把代码写复杂了。

#include <bits/stdc++.h>
#define h(x) lower_bound(a, a + k, x) - a
using namespace std;
vector<int> v;map<vector<int>, int> m;
int n, k;long long q;char a[100050], s[100050];
int main()
{
    scanf("%d%s", &n, s);strcpy(a, s);sort(a, a + n);
    m[v = vector<int>(k = unique(a, a + n) - a, 0)] = 1;
    for (int i = 0; i < n; ++i)
    {
        if (s[i] != a[0]) ++v[h(s[i])];
        else {for (auto &x : v) --x;++v[0];}
        (q += m[v]++) %= 1000000007;
    }
    return printf("%lld", q), 0;
}

目前最优解 rk 1。