比赛回顾

杭电多校再度翻车，之前几次事故都是因为题不对口，然而这次是有很多签到题。原因一方面是榜被带歪了，更多原因是我太执拗吊在 1012 题上 4 个小时不肯放弃（曹佬不劝我估计彻底吊死了，想不通为什么这题过这么多支队伍），回过头来看其他题时已经太迟了，最后也是再次拖了队伍 🦵。同校的其他两个队伍都过了 6 道题，这次实属不应该也是立刻滚来补题

前期：曹佬昨晚上打 CF 太累估计睡过头了把比赛的事给忘了开赛时还在宿舍跑过来的路上。我就先把 1010 题给签到了，然后噩梦开始我们跟榜一起看 1012 题，题意很简单但是一直降不下来复杂度，曹佬和 carry 看了一个小时候放弃转去做 1003 题，我始终觉得 1012 题思路就要出来了，一直再找规律

中期：没过多久曹佬和 carry 就把 1003 题过了，carry 回过头问了下我进展如何，我当时推规律正嗨便继续想 😓，曹佬和 carry 又跟榜去做 1007 题，中途看群里说 1012 题 O(26n) 的复杂度都可能被卡常，我当时心凉了一大截（还觉得 O(nlogn) 能过呢

后期：曹佬和 carry 1007 题也是遇见了困难，WA 了好多次才过。然而我 1012 题还是没有想出个所以然，没想到榜竟然是歪的（1012 题自从过了 300 支队伍后几乎没变，其他题的过题数都超过了 1012 题），这时我才明白可能这题根本就不是找规律，听了曹佬的劝后跟榜看 1008 题，曹佬看 1005 题，然而时间来不及了最终也是 3 道题无奈收场

赛后个人总结：

  • 犯了比赛大忌自己一直卡在一道题上连榜都不跟，导致队伍变成了两个人比赛
  • 1008 题也很简单，但是比赛时还是想复杂了模拟写了一大堆没用的

1003.Fall with Trees—凸包+等比公式

题意：在一个笛卡尔坐标系按照题目给定的规则向下画完美二叉树，给出根节点及其两个子节点的坐标，求第 1 层到第 k 层所有的节点组成凸包的面积

思路：这题样例很多时间却仍然说是 1 s，不是预处理就是 O(1) 计算，比赛时曹佬是预处理了一部分计算。设第 2 层的宽度 w2 = d，则有第 k 层宽度 wk=∑i=2kd∗22−i=d(2−22−k)w_{k} = \sum\nolimits_{i=2}^{k} d*2^{2-i} = d(2-2^{2-k})，第 k 层与第 k+1 层之间的面积 Sk=hwk+wk+12S_{k}=h \frac{w_{k}+w_{k+1}}{2}。于是我们要求的整个凸包的面积

S=∑i=1k−1Sk=hd2∑i=1k−14−3∗21−iS=\sum \textstyle_{i=1}^{k-1}S_{k}=\frac{hd}{2}\sum \textstyle_{i=1}^{k-1}4-3*2^{1-i}

后面的求和部分其实就是 k-1 个 4 减去首项为 3，公比为 1/2 的等比数列前 k-1 项和。再计算出相关参数套上面的公式就可以了。另外HDU这题评测机读入特别慢，需要 C++ 快读或者 C 的读入读出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define ONLINE_JUDGE
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i, x, y) for (auto i = (x); i != (y + 1); ++i)
#define dep(i, x, y) for (auto i = (x); i != (y - 1); --i)
#ifndef ONLINE_JUDGE
#define de(...) cout << '[' << #__VA_ARGS__ << "] = " << __VA_ARGS__ << endl;
#else
#define de(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

void test_case() {
    int k;
    scanf("%d", &k);
    int xroot, yroot, xlson, ylson, xrson, yrson;
    scanf("%d%d%d%d%d%d", &xroot, &yroot, &xlson, &ylson, &xrson, &yrson);
    int h = yroot - ylson, d = xrson - xlson;
    double sum = 4 * (k - 1) - (3 - 3 * pow(0.5, k - 1)) * 2;
    printf("%.3f\n", 0.5 * h * d * sum);
}

signed main() {
#ifndef ONLINE_JUDGE
    freopen("IO\\in.txt", "r", stdin);
    freopen("IO\\out.txt", "w", stdout);
    clock_t start, end;
    start = clock();
#endif
    int _;
    scanf("%d", &_);
    for (int i = 1; i <= _; ++i) test_case();
#ifndef ONLINE_JUDGE
    end = clock();
    cout << endl
         << "Runtime: " << (double)(end - start) / CLOCKS_PER_SEC << "s\n";
#endif
    return 0;
}

1005.Link with EQ —预处理+公式推导

题意：图书馆有一个横向排列的长桌，长桌有 n 个位置。每个有人的位置相邻的两侧不能坐人，如果一个人当前有多种位置可以坐那么他会随机挑一个位置坐下，求长桌不能在坐下其他人（即按照上述规则坐满）时期望的人数

思路：设函数 f(x) 表示两侧都不靠边的长度为 x 的连续空区间中期望坐下的人数，则有公式

f(x)=f(⌊x−12⌋)+1+f((x−1)−f(⌊x−12⌋))f(x)=f(\left \lfloor \frac{x-1}{2} \right \rfloor )+1+f((x-1)- f(\left \lfloor \frac{x-1}{2} \right \rfloor))

两个更小的连续空区间期望人数加上当前选的一个位置上做的人，边界就是 f(1)=f(2)=0，因为此时区间内放人都会挨着区间两侧的人

类似的再设 g(x) 表示一个靠边一个不靠边的长度为 x 的连续空区间中坐下的人数，则有公式

g(x)={0x≤1f(x−1)x≥2g(x)=\left\{\begin{matrix} 0 & x\le1 \\f(x-1)&x\ge2 \end{matrix}\right.

那么最后设 h(x) 表示长度为 x 的桌子期望坐下的人数，则有公式

h(x)=1x∑i=1xg(i−1)+g(x−i)+1=1+2x∑i=1x−1g(i)h(x)=\frac{1}{x} { \textstyle \sum_{i=1}^{x}}g(i-1)+g(x-i)+1=1+\frac{2}{x}{\textstyle \sum_{i=1}^{x-1}g(i)}

桌子有两个边所以就是两个 g 函数组成，又因为多个可选的位置是随机的所以我们需要对每种情况的结果取期望。

根据上面的结果我们依次打表预处理出 f、g、h函数，然后 O(1) 查询就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define ONLINE_JUDGE
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i, x, y) for (auto i = (x); i != (y + 1); ++i)
#define dep(i, x, y) for (auto i = (x); i != (y - 1); --i)
#ifndef ONLINE_JUDGE
#define de(...) cout << '[' << #__VA_ARGS__ << "] = " << __VA_ARGS__ << endl;
#else
#define de(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll maxn = 1e6 + 5;
const ll mod = 1e9 + 7;

ll f[maxn], g[maxn], ans[maxn];

ll quick_pow(ll a, ll b) {
    ll ans = 1, base = a % mod;
    while (b) {
        if (b & 1) ans = ans * base % mod;
        base = base * base % mod;
        b >>= 1;
    }
    return ans % mod;
}

inline ll mul(ll a, ll b) {
    a %= mod, b %= mod;
    return (a * b) % mod;
}

inline ll pls(ll a, ll b) {
    a %= mod, b %= mod;
    return (a + b) % mod;
}

inline ll dive(ll a, ll b) {
    return mul(a, quick_pow(b, mod - 2));  //费马小定理求逆元
}

ll dfs_f(ll x) {  //两边都坐人的空区间的最大容纳人数
    if (f[x]) return f[x];
    if (x == 1 || x == 2) return 0;  //边界
    return f[x] = pls(pls(dfs_f((x - 1) >> 1), 1), dfs_f(x - 1 - ((x - 1) >> 1)));
}

void table() {
    for (ll i = 3; i <= 1000000; ++i) dfs_f(i);  //预处理f
    for (ll i = 0; i <= 1000000; ++i) {          //预处理g
        if (i == 0 || i == 1) {
            g[i] = 0;
            continue;
        }
        g[i] = pls(f[i - 1], 1);
    }
    ll sum = 0;
    for (ll i = 1; i <= 1000000; ++i) {  //利用f和g函数计算答案
        ans[i] = pls(1, dive(mul(sum, 2), i));
        sum = pls(sum, g[i]);
    }
}

void test_case() {
    ll n;
    cin >> n;
    cout << ans[n] << endl;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("IO\\in.txt", "r", stdin);
    freopen("IO\\out.txt", "w", stdout);
    clock_t start, end;
    start = clock();
#endif
    table();
    ll _;
    cin >> _;
    for (ll i = 1; i <= _; ++i) test_case();
#ifndef ONLINE_JUDGE
    end = clock();
    cout << endl
         << "Runtime: " << (double)(end - start) / CLOCKS_PER_SEC << "s\n";
#endif
    return 0;
}

1007.Link with Limit —拓扑找环+DFS+set统计分数

题意：规定一个函数 f(x)，它的 x 和结果 f(x) 都在 [1,n][1,n] 内，有递归公式 fn(x)=f(fn−1(x)) and f1(x)=f(x)f_n(x)=f(f_{n-1}(x))\space and\space f_1(x)=f(x)

，现在想知道所有的 x∈[1,n]x \in [1,n] 关于计算式 g(x)=lim⁡n→+∞1nfi(x)g(x)=\lim_{n \to +\infty } \frac{1}{n}f_i(x) 的结算结果都相同

思路：因为每个 x 的 f(x) 实际上还是指向 [1,n][1,n]，我们可以想成一个图中某个编号 x 节点的权值是 f(x) ，同时连向另一个节点编号 f(x)，那么我们连好所有的有向边后就是一个或多个联通块，每个连通块几个链最终拼成一个环，那么 g(x) 的式子就是问从编号为 x 的节点出发一直所得到的某个权值计算式是否相同，因为 n 趋向正无穷所以链上的权值最终没忽略了，计算结果就是环上的点权均值

所以我们先记录入度拓扑找环，删掉不在换上的点，然后从换上的某个起点开始计算该环走一圈所有点权均值，看是否所有的环点权均值都相同。用 set 容器存储分子和分母对这样可以避免浮点数误差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define ONLINE_JUDGE
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i, x, y) for (auto i = (x); i != (y + 1); ++i)
#define dep(i, x, y) for (auto i = (x); i != (y - 1); --i)
#ifndef ONLINE_JUDGE
#define de(...) cout << '[' << #__VA_ARGS__ << "] = " << __VA_ARGS__ << endl;
#else
#define de(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define int ll
const int maxn = 1e5 + 5;

int n;
bool flag;
int f[maxn], in[maxn];
bool vis[maxn];
set<pii> seta;  //记录g(x)

inline void init() {
    memset(in, 0, sizeof(int) * (n + 5));
    memset(vis, 0, sizeof(bool) * (n + 5));
    seta.clear();
    flag = true;
}

void dfs(int now, int tot, int cnt) {
    if (!vis[f[now]])
        vis[f[now]] = true, dfs(f[now], tot + f[now], cnt + 1);
    else {  //走完一个环计算g(x)
        int gcd = __gcd(tot, cnt);
        seta.insert({tot / gcd, cnt / gcd});  //分数统计防止误差
        if (seta.size() > 1) flag = false;
    }
}

void test_case() {
    cin >> n;
    init();
    for (int i = 1; i <= n; ++i) cin >> f[i], ++in[f[i]];  //统计每个点入度
    queue<int> que;
    for (int i = 1; i <= n; ++i)  //从起点出发寻找环
        if (!in[i]) que.push(i);
    while (que.size()) {  //走过不在环上的点
        int now = que.front();
        que.pop();
        --in[f[now]];
        if (!in[f[now]]) que.push(f[now]);
    }
    for (int i = 1; i <= n; ++i) {  //从环上的某个起点开始遍历
        if (in[i] && !vis[i]) {
            vis[i] = 1;
            dfs(i, i, 1);
            if (!flag) break;
        }
    }
    if (!flag)
        cout << "NO" << endl;
    else
        cout << "YES" << endl;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("IO\\in.txt", "r", stdin);
    freopen("IO\\out.txt", "w", stdout);
    clock_t start, end;
    start = clock();
#endif
    int _;
    cin >> _;
    for (int i = 1; i <= _; ++i) test_case();
#ifndef ONLINE_JUDGE
    end = clock();
    cout << endl
         << "Runtime: " << (double)(end - start) / CLOCKS_PER_SEC << "s\n";
#endif
    return 0;
}

1008.Smzzl with Greedy Snake—贪心+模拟DFS

题意：在笛卡尔坐标系中模拟贪吃蛇游戏，贪吃蛇开始在某个坐标并且头朝向 d 的方向，已知接下来会依次出现 n 个食物（吃掉当前食物才会出现下一个食物），贪吃蛇走一个单位长度花费 1 体力，转头一个直角花费 1体力，请输出贪吃蛇的最优动作策略使得花费的体力最少。题目保证贪吃蛇的初始位置与食物以及相邻的两个食物不会处于同一行同一列

思路：因为食物和贪吃蛇的位置都是固定的走曼哈顿距离就是移动的最小体力花费，关键是减少转头的次数即可。题目保证的位置条件意味着我们总需要向两个相邻的方向移动，我们贪心的选择假如目前的蛇头朝向就是需要前进的方向则直接前进，否则只需要旋转一个直角就可以到达一个需要前进的方向

比赛的时候没分析朝出总要两个相邻的方向移动，还复杂的考虑了相邻两个食物的位置关系是否会影响蛇头的转向策略

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define ONLINE_JUDGE
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i, x, y) for (auto i = (x); i != (y + 1); ++i)
#define dep(i, x, y) for (auto i = (x); i != (y - 1); --i)
#ifndef ONLINE_JUDGE
#define de(...) cout << '[' << #__VA_ARGS__ << "] = " << __VA_ARGS__ << endl;
#else
#define de(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;

int n;
int nowx, nowy, nowd;

struct node {
    int x, y;
} pos[maxn];

int cost(int d) {
    if (nowd == d) return 0;
    if ((nowd + 2) % 4 == d) return 2;
    return 1;
}

void search(int &d1, int &d2, int p) {
    int fi = -1, se = -1;
    if (pos[p].y > nowy) fi == -1 ? fi = 0 : se = 0;
    if (pos[p].x > nowx) fi == -1 ? fi = 1 : se = 1;
    if (pos[p].y < nowy) fi == -1 ? fi = 2 : se = 2;
    if (pos[p].x < nowx) fi == -1 ? fi = 3 : se = 3;
    if (cost(fi) > cost(se)) swap(fi, se);
    d1 = fi, d2 = se;
}

void walk(int d, int p) {
    if ((nowd + 1) % 4 == d)
        cout << "c";
    else if ((nowd + 2) % 4 == d)
        cout << "cc";
    else if ((nowd + 3) % 4 == d)
        cout << "u";
    nowd = d;
    int cnt = 0;
    if (nowd == 0)
        cnt = pos[p].y - nowy, nowy = pos[p].y;
    else if (nowd == 1)
        cnt = pos[p].x - nowx, nowx = pos[p].x;
    else if (nowd == 2)
        cnt = nowy - pos[p].y, nowy = pos[p].y;
    else
        cnt = nowx - pos[p].x, nowx = pos[p].x;
    cout << string(cnt, 'f');
}

void test_case() {
    cin >> nowx >> nowy >> nowd;
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> pos[i].x >> pos[i].y;
    int nexd = -1, finald = -1;
    for (int i = 1; i <= n; ++i) {
        search(nexd, finald, i);
        walk(nexd, i), walk(finald, i);
    }
    cout << endl;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("IO\\in.txt", "r", stdin);
    freopen("IO\\out.txt", "w", stdout);
    clock_t start, end;
    start = clock();
#endif
    int _;
    cin >> _;
    for (int i = 1; i <= _; ++i) test_case();
#ifndef ONLINE_JUDGE
    end = clock();
    cout << endl
         << "Runtime: " << (double)(end - start) / CLOCKS_PER_SEC << "s\n";
#endif
    return 0;
}

1010.Smzzl with Tropical Taste—思维+签到

题意：题目说了一大堆，理解了其实就是开始水池子里有 V 升的水，有个小孩以 p L/sL/s 的速度喝水，老头以 q L/sL/s 的速度加水，请判断是否小孩能永远喝水池里的水

思路：不用多想，如果 p>qp>q 了水池子里的水肯定某时刻喝完，否则就永远喝不完

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define ONLINE_JUDGE
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i, x, y) for (auto i = (x); i != (y + 1); ++i)
#define dep(i, x, y) for (auto i = (x); i != (y - 1); --i)
#ifndef ONLINE_JUDGE
#define de(...) cout << '[' << #__VA_ARGS__ << "] = " << __VA_ARGS__ << endl;
#else
#define de(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

void test_case() {
    double p, q;
    cin >> p >> q;
    if (p <= q)
        cout << "N0 M0R3 BL4CK 1CE TEA!" << endl;
    else
        cout << "ENJ0Y YOURS3LF!" << endl;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("IO\\in.txt", "r", stdin);
    freopen("IO\\out.txt", "w", stdout);
    clock_t start, end;
    start = clock();
#endif
    int _;
    cin >> _;
    for (int i = 1; i <= _; ++i) test_case();
#ifndef ONLINE_JUDGE
    end = clock();
    cout << endl
         << "Runtime: " << (double)(end - start) / CLOCKS_PER_SEC << "s\n";
#endif
    return 0;
}

1012.Yiwen with Sqc—公式推导+两次差分

题意：规定 sqc(s,l,r,c)sqc(s,l,r,c) 为字符串 [l,r][l,r] 区间中字符为 c 的数量，现在给出一个全是小写的字符串，计算下面的公式

∑c=97122∑i=1n∑j=insqc(s,i,j,c)2\textstyle \sum_{c=97}^{122} \textstyle \sum_{i=1}^{n} \textstyle \sum_{j=i}^{n}sqc(s,i,j,c)^2

即字符串所有子串中不同字符分别出现的次数的平方的加和

思路：数据范围 5e6 但是时间只有 1s，O(26n) 做法可能被卡常，只有 O(n) 保过。下面开始非人类的公式推导：很容易看出不同字母之间是没有影响的，分别考虑每一种字母。考虑字母 a，假设在原串中出现了 cnt 次，记字母 a 在原串中出现的第 i 个位置为 ai （a0=0,acnt=n+1a_0=0,a_{cnt}=n+1），记 leni=ai+1−ailen_i=a_{i+1}-a_i，即两个相邻 a 之间的距离。

首先固定区间的左端点与位置 1，可以发现答案就是 ∑k=1cntlenk∗k2\textstyle \sum_{k=1}^{cnt}len_k*k^2（因为当右端点在相邻两个 ai 之间移动端时候字母数量不变，故该表达式即每段长度乘以当前端到开头的字母数量）

当区间左端点不断右移，记当前位置为 pos，则当 pos≤a1pos\le a_1 时每个位置均有答案 ∑k=1cntlenk∗k2\textstyle \sum_{k=1}^{cnt}len_k*k^2，故此段对答案总贡献是 len0∗∑k=1cntlenk∗k2len_0*\textstyle \sum_{k=1}^{cnt}len_k*k^2。同样的当 pos∈(a1,a2]pos \in (a_1,a_2] 时每个位置均由答案 ∑k=2cntlenk∗(k−1)2\textstyle \sum_{k=2}^{cnt}len_k*(k-1)^2，可以发现对 posi∈(ai,ai+1]pos_i \in (a_i,a_{i+1}] 有 ∑k=i+1cntlenk∗(k−1)2\textstyle \sum_{k=i+1}^{cnt}len_k*(k-1)^2。现在设 ansi=∑k=i+1cntlenk∗(k−i)2ans_i=\textstyle \sum_{k=i+1}^{cnt}len_k*(k-i)^2

设第一重差分 difidif_i 为两个相邻 ans 的差值则有：

difi=ansi+1−ansi=∑k=i+2cntlenk∗(k−i−1)2−∑k=i+1cntlenk∗(k−i)2=∑k=i+2cntlenk∗(k−i−1)2−∑k=i+2cntlenk∗(k−i)2−leni+1∗(1)2=−∑k=i+2cntlenk∗(2k−2i−1)−leni+1dif_i=ans_{i+1}-ans_i \\ =\textstyle \sum_{k=i+2}^{cnt}len_k*(k-i-1)^2-\sum_{k=i+1}^{cnt}len_k*(k-i)^2\\ =\textstyle \sum_{k=i+2}^{cnt}len_k*(k-i-1)^2-\sum_{k=i+2}^{cnt}len_k*(k-i)^2-len_{i+1}*(1)^2\\ =-\textstyle \sum_{k=i+2}^{cnt}len_k*(2k-2i-1)-len_{i+1}

设第二重差分 diffidiff_i 为两个相邻 difidif_i 的差值则有：

diffi=difi+1−difi=−∑k=i+3cntlenk(2k−2(i+1)−1)−leni+2+∑k=i+2cntlenk∗(2k−2i−1)+leni+1=−∑k=i+3cntlenk∗(2k−2(i+1)−1)+∑k=i+3cntlenk∗(2k−2i−1)+leni+2∗3+leni+1−leni+2=∑k=i+3cntlenk∗2+leni+2∗3+leni+1−leni+2=∑k=i+3cntlenk∗2+leni+2∗2+leni+1diff_i=dif_{i+1}-dif_i\\ =-\textstyle \sum_{k=i+3}^{cnt}len_k(2k-2(i+1)-1)-len_{i+2}+\sum_{k=i+2}^{cnt}len_k*(2k-2i-1)+len_{i+1}\\ =-\textstyle \sum_{k=i+3}^{cnt}len_k*(2k-2(i+1)-1)+\sum_{k=i+3}^{cnt}len_k*(2k-2i-1)+len_{i+2}*3+len_{i+1}-len_{i+2}\\ =\textstyle \sum_{k=i+3}^{cnt}len_k*2+len_{i+2}*3+len_{i+1}-len_{i+2}\\ =\textstyle \sum_{k=i+3}^{cnt}len_k*2+len_{i+2}*2+len_{i+1}

通过上式先维护 diffdiff 的值进而维护 difdif 的值进而维护 ansans，然后将所有的 ansans 加和就是最终的答案。最终只遍历了一遍字符串的所有字母所有复杂度为 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#define ONLINE_JUDGE
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define rep(i, x, y) for (auto i = (x); i != (y + 1); ++i)
#define dep(i, x, y) for (auto i = (x); i != (y - 1); --i)
#ifndef ONLINE_JUDGE
#define de(...) cout << '[' << #__VA_ARGS__ << "] = " << __VA_ARGS__ << endl;
#else
#define de(...)
#endif
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
const ll mod = 998244353;

ll len;
vector<ll> vec[30];

ll cal(ll ch) {
    vec[ch].pb(len + 1);
    ll tot = 0, diff = 0, dif = 0;  //diff累加实际上计算的是dif,dif累加实际上计算的是某个区间的ans
    rep(i, 1, vec[ch].size() - 1) {
        tot = tot + dif * (vec[ch][i] - vec[ch][i - 1]) % mod;
        diff = diff + 2 * vec[ch][i - 1] + vec[ch][i] - vec[ch][i - 1] % mod;
        dif = dif + diff % mod;
    }
    return tot;
}

void test_case() {
    string str;
    cin >> str;
    len = str.size();
    str = " " + str;
    rep(i, 0, 25) vec[i].clear(), vec[i].pb(0);
    rep(i, 1, len) vec[str[i] - 'a'].pb(i);
    ll ans = 0;
    rep(i, 0, 25) ans = ans + cal(i) % mod;
    cout << ans % mod << endl;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("IO\\in.txt", "r", stdin);
    freopen("IO\\out.txt", "w", stdout);
    clock_t start, end;
    start = clock();
#endif
    ll _;
    cin >> _;
    for (ll i = 1; i <= _; ++i) test_case();
#ifndef ONLINE_JUDGE
    end = clock();
    cout << endl
         << "Runtime: " << (double)(end - start) / CLOCKS_PER_SEC << "s\n";
#endif
    return 0;
}