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

## Sol

NOI的题都这么良心么。。

hash优化一下 => 90

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

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;
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;
}

0 条评论

• ### 洛谷P3346 [ZJOI2015]诸神眷顾的幻想乡(广义后缀自动机)

因为所有合法的答案一定是某个叶子节点为根的树上的一条链，因此这样可以统计出所有合法的答案

• ### 经典面试题

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明...

• ### 洛谷P4064 [JXOI2017]加法(贪心 差分)

首先二分一个答案，然后check是否可行。check的时候我们需要对每个位置$$i$$，维护出所有左端点在$$i$$左侧，右端点在$$i$$右侧的所有区间。最优...

• ### linux网络编程之System V 共享内存 和 系列函数

跟消息队列一样，共享内存也有自己的数据结构，如下： struct shmid_ds { struct ipc_perm shm_perm;    /* Ow...

• ### 三行代码接入，社交软件打字时底下弹出的表情布局,自定义ViewPager+页面点标+各种功能的android小框架。

(转载请声明出处：https://cloud.tencent.com/developer/user/1148436/activities) 前言：       ...

• ### 羊皮书APP（Android版）开发系列（二十一）双联动分组ListView，类似于外卖点餐

ok,到这里就完成了双ListView联动的实现，可以到这里下载运行体验https://github.com/wjie2014/DoubleListViewLi...

• ### UNREFERENCED_PARAMETER的作用

UNREFERENCED_PARAMETER 的作用 2007年06月16日 星期六 14:38 我们从 UNREFERENCED_PARAMETER 开始...

• ### HDU 3829 Cat VS Dog(二分图最大独立集)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3829