50pts求组
查看原帖
50pts求组
1183187
sxhy楼主2024/9/16 17:41
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 2e6 + 7;
const int M = 3e4 + 7;
const long long mod = 131;
#define up(i,l,r) for(int i=l;i<=r;i++)
#define dn(i,l,r) for(int i=l;i>=r;i--)
#define mms(k,p) memset(k,p,sizeof(k))
#define pr(c) printf("%lld\n",c)
ull n, m, res, ans, tot;
ull ha[N], base[N];
ull len[N];
char ch[N];
unordered_map<ull, ll>ma;
int main() {
	base[0] = 1;
	cin >> n;
	up(i,1,n) {
		scanf("%lld",&len[i]);
		ull tmp = 0;
		up(j,1,len[i]) {
			++tot;
			scanf(" %c", &ch[tot]);
			tmp = tmp*mod + ch[tot];
		}
		ma[tmp] = 1;
	}
	up(i, 1, tot) {
		base[i] = base[i - 1] * mod;
	}
	ll sum=0;
	up(i,1,n) {
		ha[0] = 0;
		up(k, 1, len[i]) {
			ha[k] = ha[k - 1] * mod + ch[k+sum];
		}
		up(j,1,len[i]-1) {
			ll now_len = j + len[i];
			ha[j+len[i]] = ha[len[i] + j - 1] * mod + ch[j+sum];
			ull ha1 = ha[now_len] -
				ha[(now_len - now_len / 2)] * base[now_len / 2];
			if (ha[now_len / 2] == ha1
				&& ma[ha1]
				) {
				ans++;
			}

		}
		sum += len[i];
	}
	pr(ans*2+n);
}
2024/9/16 17:41
加载中...