CF1129C Morse Code 题解

int a[N], f[3010][3010];
// f[i][j]: [i,j] 段内可以划分出多少个本质不同的，之前从未出现过的合法字母串
// 哎是不是不同的字符串一定不会得到相同的摩码（?
ull h[N], bit[N];
const ull base = 13331;
inline ull get(int l, int r) { return h[r] - h[l - 1] * bit[r - l + 1]; }
inline int chk(int l, int r) {
    int len = r - l + 1;
    if (len < 4) return 1;
    if (a[l] == 0 && a[l + 1] == 0 && a[l + 2] == 1 && a[l + 3] == 1) return 0;
    if (a[l] == 0 && a[l + 1] == 1 && a[l + 2] == 0 && a[l + 3] == 1) return 0;
    if (a[l] == 1 && a[l + 1] == 1 && a[l + 2] == 1 && a[l + 3] == 0) return 0;
    if (a[l] == 1 && a[l + 1] == 1 && a[l + 2] == 1 && a[l + 3] == 1) return 0;
    return 1;
}
struct Hasher {
    const int mod = 1000007;
    vector<ull> Hash[1000007];
    inline void ins(ull x) {
        Hash[x % mod].emplace_back(x);
    }
    inline int qry(ull x) {
        for (ull &i : Hash[x % mod])
            if (i == x) return 1;
        return 0;
    }
} se;
inline void sol() {
    bit[0] = 1;
    for (int i = 1; i < N; ++i) bit[i] = bit[i - 1] * base;
    int m, res = 0; cin >> m;
    for (int i = 1; i <= m; ++i) {
        int x; cin >> x, a[i] = x;
        f[i][i - 1] = 1, h[i] = h[i - 1] * base + x + 1;
        for (int j = 1; j <= i; ++j) {
            for (int k = 0; k < 4; ++k)
                if (i >= j + k && chk(i - k, i)) f[j][i] = (f[j][i] + f[j][i - k - 1]) % mod;
            if (!se.qry(get(j, i))) res = (res + f[j][i]) % mod, se.ins(get(j, i));
        } cout << res << '\n';
    }
}