BZOJ4650: [Noi2016]优秀的拆分(hash 调和级数)
程序员文章站
2022-06-29 13:31:11
题意 "题目链接" Sol NOI的题都这么良心么。。 先交个$n^4$暴力 = 75 hash优化一下 = 90 然后$90$到$100$分之间至少差了$10$难度台阶= = $90$分的暴力hash就比较trival了。 考虑怎么优化。 显然我们只要找出所有形如$AA$的字符串就行了,设$pre ......
题意
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; }
下一篇: C++类与对象的详细说明2