首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >BZOJ4650: [Noi2016]优秀的拆分(hash 调和级数)

BZOJ4650: [Noi2016]优秀的拆分(hash 调和级数)

作者头像
attack
发布2018-12-24 10:00:48
3880
发布2018-12-24 10:00:48
举报

题意

题目链接

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;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-12-05 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题意
  • Sol
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档