c/c++语言开发共享BZOJ4650: [Noi2016]优秀的拆分(hash 调和级数)

题意

题目链接

sol

noi的题都这么良心么。。

先交个(n^4)暴力 => 75

hash优化一下 => 90

然后(90)到(100)分之间至少差了(10)难度台阶= =

(90)分的暴力hash就比较trival了。

考虑怎么优化。 显然我们只要找出所有形如(aa)的字符串就行了，设(pre[i])表示以(i)为端点，向前的所有(aa)的数量，(suf[i])表示以(i)为端点，向后的所有(aa)的数量

这样最终答案就是(sum_{i = 1}^{n – 1} pre[i] * suf[i + 1])

那怎么求(pre)呢？((suf)同理，只要把原串翻转一下就和pre一样了)

首先枚举一个长度(len)，然后每隔(len)个点打一个标记。

比如(abcabca)在长度为(len = 3)的时候是这样的(abc|abc|a)

对于相邻的两个标记，我们二分找出他们的(lcs)和(lis)，然后考虑在第一个标记左端点的所有点的贡献，一个显然的结论是：(其实也不是很显然，自己举几个例子试试吧)

在([(i – pre + 1, min(i, i – pre + 1 + (pre + suf – len )) + 1]))内的点会产生贡献(可能不是很严格，但是可以a。。)

然后暴力加就可以a了(因为数据水。。)

实际上可以直接差分一波

时间复杂度:(o(nlog^2n))

mmp居然卡unsigned 自然溢出

#include<bits/stdc++.h> #define ull unsigned long long  #define ll long long  using namespace std; const int maxn = 1e5 + 10, mod = 998244353; inline ll read() {     char c = getchar(); int x = 0, f = 1;     while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}     while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();     return x * f; } int n, sum1[maxn], sum2[maxn];  ull ha[maxn], base = 123, po[maxn]; char s[maxn]; ull gethash(int l, int r) {     if(l <= 0) return ha[r];     return (ha[r] - ha[l - 1] * po[r - l + 1] % mod + mod) % mod; } void get(char *a, int *sum) {     po[0] = 1; ha[0] = 0; memset(ha, 0, sizeof(ha));     for(int i = 1; i <= n; i++) ha[i] = (ha[i - 1] * base % mod + a[i]) % mod, po[i] = base * po[i - 1] % mod;     for(int len = 1; len <= n / 2 + 1; len++) {          for(int i = len; i < n; i += len) {             int ll = i, rr = i + len, l = 0, r = 0, pre = 0, suf = 0, ans = 0;             if(rr > n) continue;             l = 1, r = len; ans = 0;             while(l <= r) {                 int mid = l + r >> 1;                 if(gethash(ll - mid + 1, ll) == gethash(rr - mid + 1, rr)) l = mid + 1, ans = mid;                 else r = mid - 1;             }             pre = ans;             l = 1, r = len; ans = 0;             while(l <= r) {                 int mid = l + r >> 1;                 if(gethash(ll + 1, ll + mid) == gethash(rr + 1, rr + mid)) l = mid + 1, ans = mid;                 else r = mid - 1;             }             suf = ans;             if(pre + suf < len) continue;             //for(int j = i - pre + 1; j <= min(i, i - pre + 1 + (pre + suf - len )); j++) sum[j]++;             sum[i - pre + 1]++;             sum[min(i, i - pre + 1 + (pre + suf - len )) + 1]--;         }     }     for(int i = 1; i <= n; i++) sum[i] += sum[i - 1]; } void solve() {     memset(sum1, 0, sizeof(sum1));     memset(sum2, 0, sizeof(sum2));     scanf("%s", s + 1); n = strlen(s + 1);     get(s, sum1);     reverse(s + 1, s + n + 1);     get(s, sum2);     reverse(sum2 + 1, sum2 + n + 1);     ll ans = 0;     for(int i = 1; i <= n - 1; i++) ans += sum1[i + 1] * sum2[i];     cout << ans << endl; }   signed main() {     //freopen("a.in", "r", stdin);     for(int t = read(); t; t--, solve());     return 0; }