2021“MINIEYE杯”中国大学生算法设计超级联赛（7）Yiwen with Sqc 字符串

2021“MINIEYE杯”中国大学生算法设计超级联赛（7）Yiwen with Sqc 字符串 😊 | Powered By HeartFireY

Problem Analysis

题目大意：定义一个字符串的权值为字符串中不同字符出现次数的平方和，求给定字符串所有子串的贡献值之和。

数据范围猛如虎，暴力枚举不可取。

首先我们明确：某个字符串而言，每个字母出现次数平方和对答案的贡献是相互独立的，因为我们对于每个字母统计其出现的次数和出现的位置，单独计算其贡献即可。

那么我们来考虑对于单个字母，如何计算其对整个答案的贡献？

我们定义某个字母的 t i m e s [ i ] times[i] times[i]​表示在整个字符串中截至 i i i​​​位置为止，字母出现的次数，那么对于某个区间 [ i , j ] [i, j] [i,j]​而言，其出现次数的平方为 ( t i m e s [ j ] − t i m e s [ i − 1 ] ) 2 (times[j] - times[i - 1])^2 (times[j]−times[i−1])2​，那么对于整个字符串而言，某个字母的贡献可以表示为​​： a n s s u b = ∑ i = 1 n ∑ j = i n ( t i m e s [ j ] − t i m e s [ i − 1 ] ) 2 ans_{sub} = \sum^{n}_{i = 1}\sum^{n}_{j = i}(times[j] - times[i - 1])^2 anssub​=i=1∑n​j=i∑n​(times[j]−times[i−1])2 我们需要继续对上式进行化简： a n s s u b = ∑ i = 1 n ∑ j = i n ( t i m e s [ j ] − t i m e s [ i − 1 ] ) 2 = ∑ i = 1 n ∑ j = i n t i m e s [ j ] 2 − 2 ∑ i = 1 n ∑ j = i n t i m e s [ j ] t i m e s [ i − 1 ] + ∑ i = 1 n ∑ j = i n t i m e s [ i − 1 ] 2 = ∑ i = 1 n ∑ j = i n t i m e s [ j ] 2 + ∑ i = 1 n ∑ j = i n t i m e s [ i − 1 ] 2 − 2 ∑ i = 1 n t i m e s [ i − 1 ] ∑ j = i n t i m e s [ j ] \begin{aligned} ans_{sub} &= \sum^{n}_{i = 1}\sum^{n}_{j = i}(times[j] - times[i - 1])^2 \\ &= \sum^{n}_{i = 1}\sum^{n}_{j = i}times[j]^2 - 2\sum^{n}_{i = 1}\sum^{n}_{j = i}times[j]times[i - 1]+\sum^{n}_{i = 1}\sum^{n}_{j = i}times[i - 1]^2 \\ &= \sum^{n}_{i = 1}\sum^{n}_{j = i}times[j]^2 + \sum^{n}_{i = 1}\sum^{n}_{j = i}times[i - 1]^2 - 2\sum^{n}_{i = 1}times[i - 1]\sum^{n}_{j = i}times[j] \\ \end{aligned} anssub​​=i=1∑n​j=i∑n​(times[j]−times[i−1])2=i=1∑n​j=i∑n​times[j]2−2i=1∑n​j=i∑n​times[j]times[i−1]+i=1∑n​j=i∑n​times[i−1]2=i=1∑n​j=i∑n​times[j]2+i=1∑n​j=i∑n​times[i−1]2−2i=1∑n​times[i−1]j=i∑n​times[j]​ 展开最后一项 2 ∑ i = 1 n t i m e s [ i − 1 ] ∑ j = i n t i m e s [ j ] 2\sum^{n}_{i = 1}times[i - 1]\sum^{n}_{j = i}times[j] 2∑i=1n​times[i−1]∑j=in​times[j]​为求和矩阵形式（以下暂时简写为 t t t）​ 2 × [ t [ 0 ] × t [ 1 ] t [ 0 ] × t [ 2 ] t [ 0 ] × t [ 3 ] t [ 0 ] × t [ 4 ] . . . t [ 0 ] × t [ n ] 0 t [ 1 ] × t [ 2 ] t [ 1 ] × t [ 3 ] t [ 1 ] × t [ 4 ] . . . t [ 1 ] × t [ n ] 0 0 t [ 2 ] × t [ 3 ] t [ 2 ] × t [ 4 ] . . . t [ 2 ] × t [ n ] 0 0 0 t [ 3 ] × t [ 4 ] . . . t [ 3 ] × t [ n ] . . . . . . . . . . . . . . . . . . 0 0 0 0 . . . t [ n − 1 ] × t [ n ] ] 2 \times \begin{matrix} \left[ \begin{array}{cccccc} t[0] \times t[1] & t[0] \times t[2] & t[0] \times t[3] & t[0] \times t[4] & ... & t[0] \times t[n] \\ 0 & t[1] \times t[2] & t[1] \times t[3] & t[1] \times t[4] & ... & t[1] \times t[n] \\ 0 & 0 &t[2] \times t[3] & t[2] \times t[4] & ... & t[2] \times t[n] \\ 0 & 0 & 0 & t[3] \times t[4] & ... & t[3] \times t[n] \\ ... & ... & ... & ... & ... & ... \\ 0 & 0 & 0 & 0 & ... & t[n - 1] \times t[n] \\ \end{array} \right] \end{matrix} 2×⎣⎢⎢⎢⎢⎢⎢⎡​t[0]×t[1]000...0​t[0]×t[2]t[1]×t[2]00...0​t[0]×t[3]t[1]×t[3]t[2]×t[3]0...0​t[0]×t[4]t[1]×t[4]t[2]×t[4]t[3]×t[4]...0​..................​t[0]×t[n]t[1]×t[n]t[2]×t[n]t[3]×t[n]...t[n−1]×t[n]​⎦⎥⎥⎥⎥⎥⎥⎤​​ 将原始式子展开 [ t [ 1 ] 2 t [ 2 ] 2 t [ 3 ] 2 t [ 4 ] 2 . . . t [ n ] 2 0 ( t [ 2 ] − t [ 1 ] ) 2 ( t [ 3 ] − t [ 1 ] ) 2 ( t [ 4 ] − t [ 1 ] ) 2 . . . ( t [ n ] − t [ 1 ] ) 2 0 0 ( t [ 3 ] − t [ 2 ] ) 2 ( t [ 4 ] − t [ 2 ] ) 2 . . . ( t [ n ] − t [ 2 ] ) 2 0 0 0 ( t [ 4 ] − t [ 3 ] ) 2 . . . ( t [ n ] − t [ 3 ] ) 2 . . . . . . . . . . . . . . . . . . 0 0 0 0 . . . ( t [ n ] − t [ n − 1 ] ) 2 ] \begin{matrix} \left[ \begin{array}{cccccc} t[1]^2 & t[2]^2 & t[3]^2 & t[4]^2 & ... & t[n]^2 \\ 0 & (t[2] - t[1])^2 & (t[3] - t[1])^2 & (t[4] - t[1])^2 & ... & (t[n] - t[1])^2 \\ 0 & 0 & (t[3] - t[2])^2 & (t[4] - t[2])^2 & ... & (t[n] - t[2])^2 \\ 0 & 0 & 0 & (t[4] - t[3])^2 & ... & (t[n] - t[3])^2 \\ ... & ... & ... & ... & ... & ... \\ 0 & 0 & 0 & 0 & ... & (t[n] - t[n - 1])^2 \\ \end{array} \right] \end{matrix} ⎣⎢⎢⎢⎢⎢⎢⎡​t[1]2000...0​t[2]2(t[2]−t[1])200...0​t[3]2(t[3]−t[1])2(t[3]−t[2])20...0​t[4]2(t[4]−t[1])2(t[4]−t[2])2(t[4]−t[3])2...0​..................​t[n]2(t[n]−t[1])2(t[n]−t[2])2(t[n]−t[3])2...(t[n]−t[n−1])2​⎦⎥⎥⎥⎥⎥⎥⎤​​ 将第二行至最后一行展开，可得： [ t [ 1 ] 2 t [ 2 ] 2 t [ 3 ] 2 t [ 4 ] 2 . . . t [ n ] 2 0 ( t [ 2 ] 2 + t [ 1 ] 2 − 2 t [ 1 ] t [ 2 ] ) ( t [ 3 ] 2 + t [ 1 ] 2 − 2 t [ 1 ] t [ 3 ] ) ( t [ 4 ] 2 + t [ 1 ] 2 − 2 t [ 1 ] t [ 4 ] ) . . . ( t [ n ] 2 + t [ 1 ] 2 − 2 t [ 1 ] t [ n ] ) 0 0 ( t [ 3 ] 2 + t [ 2 ] 2 − 2 t [ 2 ] t [ 3 ] ) ( t [ 4 ] 2 + t [ 2 ] 2 − 2 t [ 2 ] t [ 4 ] ) . . . ( t [ n ] 2 + t [ 2 ] 2 − 2 t [ 2 ] t [ n ] ) 0 0 0 ( t [ 4 ] 2 + t [ 3 ] 2 − 2 t [ 3 ] t [ 4 ] ) . . . ( t [ n ] 2 + t [ 3 ] 2 − 2 t [ 3 ] t [ n ] ) . . . . . . . . . . . . . . . . . . 0 0 0 0 . . . ( t [ n ] 2 + t [ n − 1 ] 2 − 2 t [ n − 1 ] t [ n ] ) ] \begin{matrix} \left[ \begin{array}{cccccc} t[1]^2 & t[2]^2 & t[3]^2 & t[4]^2 & ... & t[n]^2 \\ 0 & (t[2]^2 + t[1]^2 - 2t[1]t[2]) & (t[3]^2 + t[1]^2 - 2t[1]t[3]) & (t[4]^2 + t[1]^2 - 2t[1]t[4]) & ... & (t[n]^2 + t[1]^2 - 2t[1]t[n]) \\ 0 & 0 & (t[3]^2 + t[2]^2 - 2t[2]t[3]) & (t[4]^2 + t[2]^2 - 2t[2]t[4]) & ... & (t[n]^2 + t[2]^2 - 2t[2]t[n]) \\ 0 & 0 & 0 & (t[4]^2 + t[3]^2 - 2t[3]t[4]) & ... & (t[n]^2 + t[3]^2 - 2t[3]t[n]) \\ ... & ... & ... & ... & ... & ... \\ 0 & 0 & 0 & 0 & ... & (t[n]^2 + t[n - 1]^2 - 2t[n - 1]t[n]) \\ \end{array} \right] \end{matrix} ⎣⎢⎢⎢⎢⎢⎢⎡​t[1]2000...0​t[2]2(t[2]2+t[1]2−2t[1]t[2])00...0​t[3]2(t[3]2+t[1]2−2t[1]t[3])(t[3]2+t[2]2−2t[2]t[3])0...0​t[4]2(t[4]2+t[1]2−2t[1]t[4])(t[4]2+t[2]2−2t[2]t[4])(t[4]2+t[3]2−2t[3]t[4])...0​..................​t[n]2(t[n]2+t[1]2−2t[1]t[n])(t[n]2+t[2]2−2t[2]t[n])(t[n]2+t[3]2−2t[3]t[n])...(t[n]2+t[n−1]2−2t[n−1]t[n])​⎦⎥⎥⎥⎥⎥⎥⎤​​ 将平方项全部提取出来，可得：

n ∑ i = 1 n t [ i ] 2 + [ 0 0 0 0 . . . 0 0 − 2 t [ 1 ] t [ 2 ] − 2 t [ 1 ] t [ 3 ] − 2 t [ 1 ] t [ 4 ] . . . − 2 t [ 1 ] t [ n ] 0 0 − 2 t [ 2 ] t [ 3 ] − 2 t [ 2 ] t [ 4 ] . . . − 2 t [ 2 ] t [ n ] 0 0 0 − 2 t [ 3 ] t [ 4 ] . . . − 2 t [ 3 ] t [ n ] . . . . . . . . . . . . . . . . . . 0 0 0 0 . . . − 2 t [ n − 1 ] t [ n ] ] n\sum^{n}_{i =1} t[i]^2 + \begin{matrix} \left[ \begin{array}{cccccc} 0 & 0 & 0 & 0 & ... & 0 \\ 0 & - 2t[1]t[2] & - 2t[1]t[3] & - 2t[1]t[4] & ... & - 2t[1]t[n] \\ 0 & 0 & - 2t[2]t[3] & - 2t[2]t[4] & ... & - 2t[2]t[n] \\ 0 & 0 & 0 & - 2t[3]t[4] & ... & - 2t[3]t[n] \\ ... & ... & ... & ... & ... & ... \\ 0 & 0 & 0 & 0 & ... & - 2t[n - 1]t[n] \\ \end{array} \right] \end{matrix} ni=1∑n​t[i]2+⎣⎢⎢⎢⎢⎢⎢⎡​0000...0​0−2t[1]t[2]00...0​0−2t[1]t[3]−2t[2]t[3]0...0​0−2t[1]t[4]−2t[2]t[4]−2t[3]t[4]...0​..................​0−2t[1]t[n]−2t[2]t[n]−2t[3]t[n]...−2t[n−1]t[n]​⎦⎥⎥⎥⎥⎥⎥⎤​​ 对求和矩阵再变换：整个式子 + ∑ i = 1 n t [ i ] 2 − ∑ i = 1 n t [ i ] 2 +\sum^{n}_{i =1} t[i]^2 - \sum^{n}_{i =1} t[i]^2 +∑i=1n​t[i]2−∑i=1n​t[i]2​不变，则变为： ( n + 1 ) ∑ i = 1 n t [ i ] 2 − [ t [ 1 ] t [ 1 ] t [ 2 ] t [ 2 ] t [ 3 ] t [ 3 ] t [ 4 ] t [ 4 ] . . . t [ n ] t [ n ] 0 2 t [ 1 ] t [ 2 ] 2 t [ 1 ] t [ 3 ] 2 t [ 1 ] t [ 4 ] . . . 2 t [ 1 ] t [ n ] 0 0 2 t [ 2 ] t [ 3 ] 2 t [ 2 ] t [ 4 ] . . . 2 t [ 2 ] t [ n ] 0 0 0 2 t [ 3 ] t [ 4 ] . . . 2 t [ 3 ] t [ n ] . . . . . . . . . . . . . . . . . . 0 0 0 0 . . . 2 t [ n − 1 ] t [ n ] ] (n + 1)\sum^{n}_{i =1} t[i]^2 - \begin{matrix} \left[ \begin{array}{cccccc} t[1]t[1] & t[2]t[2] & t[3]t[3] & t[4]t[4] & ... & t[n]t[n] \\ 0 & 2t[1]t[2] & 2t[1]t[3] & 2t[1]t[4] & ... & 2t[1]t[n] \\ 0 & 0 & 2t[2]t[3] & 2t[2]t[4] & ... & 2t[2]t[n] \\ 0 & 0 & 0 & 2t[3]t[4] & ... & 2t[3]t[n] \\ ... & ... & ... & ... & ... & ... \\ 0 & 0 & 0 & 0 & ... & 2t[n - 1]t[n] \\ \end{array} \right] \end{matrix} (n+1)i=1∑n​t[i]2−⎣⎢⎢⎢⎢⎢⎢⎡​t[1]t[1]000...0​t[2]t[2]2t[1]t[2]00...0​t[3]t[3]2t[1]t[3]2t[2]t[3]0...0​t[4]t[4]2t[1]t[4]2t[2]t[4]2t[3]t[4]...0​..................​t[n]t[n]2t[1]t[n]2t[2]t[n]2t[3]t[n]...2t[n−1]t[n]​⎦⎥⎥⎥⎥⎥⎥⎤​​ 将后面的求和矩阵继续化简，第 2 2 2行至 n n n行的 2 × x 2 \times x 2×x项全部展开为 x + x x + x x+x形式，然后加和合并同类项，可得： ( n + 1 ) ∑ i = 1 n t i m e s [ i ] 2 − ∑ i = 1 n t i m e s [ i ] ∑ i = 1 n t i m e s [ i ] = ( n + 1 ) ∑ i = 1 n t i m e s [ i ] 2 − ( ∑ i = 1 n t i m e s [ i ] ) 2 (n + 1)\sum^{n}_{i = 1} times[i]^2 - \sum^{n}_{i = 1}times[i]\sum^{n}_{i = 1}times[i] = (n + 1)\sum^{n}_{i = 1} times[i]^2 - (\sum^{n}_{i = 1}times[i])^2 (n+1)i=1∑n​times[i]2−i=1∑n​times[i]i=1∑n​times[i]=(n+1)i=1∑n​times[i]2−(i=1∑n​times[i])2 即： a n s s u b = ( n + 1 ) ∑ i = 1 n t i m e s [ i ] 2 − ( ∑ i = 1 n t i m e s [ i ] ) 2 ans_{sub} = (n + 1)\sum^{n}_{i = 1} times[i]^2 - (\sum^{n}_{i = 1}times[i])^2 anssub​=(n+1)i=1∑n​times[i]2−(i=1∑n​times[i])2 根据这个推导式，我们可以在 O ( 26 × n ) O(26 \times n) O(26×n)​内求出答案，但还不够快，我们可以继续优化：

考虑 t i m e s [ i ] times[i] times[i]的意义：到 i i i为止，指定字母出现的个数。再考虑 t i m e s [ i ] times[i] times[i]的计算方法：前缀和。那么很容易联想到前缀和的递推形式：对于字母没有出现的某连续位置 j ， k . . . j，k... j，k...，一定有 t i m e s [ j ] = t i m e s [ k ] = t i m e s [ …   ] times[j] = times[k] = times[\dots] times[j]=times[k]=times[…]​，那么显然，相邻(未必连续)的两个字母出现位置之间的区间，都有这个性质，也就是说，区间的长度影响前缀和的值。

我们预处理出某字母出现位置的下标，按照 1 … n 1 \dots n 1…n​的下标顺序存在数组 v e c vec vec​中，即 v e c [ i ] vec[i] vec[i]​表示序列中第 i i i个该字母出现的位置下标。那么我们可以根据 v e c vec vec来计算每段区间长度。于是我们将这条规律写成表达式的形式： t i m e s [ i ] = ∑ i = 1 l e n n ( i × ( v e c [ i + 1 ] − v e c [ i ] ) ) times[i] = \sum^{lenn}_{i = 1}(i \times (vec[i + 1] - vec[i])) times[i]=i=1∑lenn​(i×(vec[i+1]−vec[i])) 我们要求的 ∑ i = 1 n t i m e s [ i ] 2 \sum^{n}_{i = 1} times[i]^2 ∑i=1n​times[i]2也可以同样表示为： ∑ i = 1 n t i m e s [ i ] 2 = ∑ i = 1 l e n n ( i × i × ( v e c [ i + 1 ] − v e c [ i ] ) ) \sum^{n}_{i = 1} times[i]^2 = \sum^{lenn}_{i = 1}(i \times i \times (vec[i + 1] - vec[i])) i=1∑n​times[i]2=i=1∑lenn​(i×i×(vec[i+1]−vec[i])) 那么我们一开始的 a n s s u b ans_{sub} anssub​的最简表示形式(可以认为属于某种最简形式)便可以得出： a n s s u b = ∑ i = 1 l e n n ( i × i × ( v e c [ i + 1 ] − v e c [ i ] ) ) + ( ∑ i = 1 l e n n ( i × ( v e c [ i + 1 ] − v e c [ i ] ) ) ) 2 ans_{sub} = \sum^{lenn}_{i = 1}(i \times i \times (vec[i + 1] - vec[i])) + (\sum^{lenn}_{i = 1}(i \times (vec[i + 1] - vec[i])))^2 anssub​=i=1∑lenn​(i×i×(vec[i+1]−vec[i]))+(i=1∑lenn​(i×(vec[i+1]−vec[i])))2 答案不要忘记对 998244353 998244353 998244353取模。​

Accepted Code

#include 
#define int long long
using namespace std;

const int MOD = 998244353;

int calc(vector vec, int lenn){
    vec.push_back(lenn + 1);
    int sub1 = 0, sub2 = 0, ans = 0;
    for(int i = 1; i > s;
    int lenn = s.length(), ans = 0;
    s = ' ' + s + '\0';
    vector a[30];
    for(int i = 0; i