另外一种做法,求调。
查看原帖
另外一种做法,求调。
700558
williamwei楼主2024/6/30 17:23
#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxm = 1e6 + 10;
const int mod = 1e9 + 7;
const int N = 1e6;
const int B = 281;
const int P = 1222827239;
int n, ls, lt, S, ans, f[maxm], g[maxm], h[maxm], p[maxm], b[maxm];
char s[maxm], t[maxm];
int val1(int l, int r) { return (p[r] - (ll)p[l - 1] * b[r - l + 1] % P + P) % P; }
int query1(int k, int x) {return x < k ? p[x] : ((ll)p[k - 1] * b[x - k + 1] + val1(k + 1, x + 1)) % P; }
int val2(int l, int r) { return (h[r] - (ll)h[l - 1] * b[r - l + 1] % P + P) % P; }
int query2(int k, int x) {return x < k ? h[x] : ((ll)h[k - 1] * b[x - k + 1] + val2(k + 1, x + 1)) % P; }
int find(int b1, int b2) {
	int l = 0, r = min(lt - (b1 == lt + 1), ls - (b2 == ls + 1)), res = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (query1(b1, mid) == query2(b2, mid)) 
			l = mid + 1, res = mid;
		else r = mid - 1;
	} 
	return res + 1;
} // 以上没问题 
int calc(int x) {
	int k1 = find(lt + 1, x), 
		k2 = find(k1, x);
	if (t[k1] > s[k1 + (k1 > x)]) {
		if (t[k1 + 1] > s[k1 + (k1 > x)]) return 0;
		else return (t[k2 + (k2 > k1)] < s[k2 + (k2 > x)]) * f[k1];
	}
	else {S -= f[x + 1]; return S + g[k1 - 1] + (t[k2 + (k2 > k1)] < s[k2 + (k2 > x)]) * f[k1];}
}
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> t + 1;
	lt = strlen(t + 1); 
	b[0] = 1; 
	S = lt;
    for (int i = 1; i <= N; i++) 
		b[i] = (ll)b[i - 1] * B % P;
    for (int i = 1; i <= lt + 1; i++) 
		f[i] = 1, g[i] = g[i - 1] + (t[i] >= t[i + 1]);
    for (int i = 1; i <= lt + 1; i++) 
		p[i] = ((ll)p[i - 1] * B + t[i]) % P;
    for (int j = 2; j <= n; j++) {
        cin >> s + 1; 
		ls = strlen(s + 1);
        for (int i = 1; i <= ls; i++) 
			h[i] = ((ll)h[i - 1] * B + s[i]) % P;
        for (int i = 1; i <= ls + 1; i++) f[i] = calc(i);
        for (int i = 1; i <= ls; i++) t[i] = s[i]; 
        lt = ls; 
		for (int i = 1; i <= ls + 1; i++) p[i] = h[i];
        for (int i = 1; i <= ls + 1; i++) 
			g[i] = (g[i - 1] + (s[i] >= s[i + 1]) * f[i]) % mod;
        S = 0; 
		for (int i = 2; i <= ls + 1; i++) S += f[i];
    }
    for (int i = 1; i <= ls + 1; i++) ans += f[i];
    cout << ans << '\n';
    return 0;
}
2024/6/30 17:23
加载中...