P9753 题解

sinsop90 · 2023-10-29 20:33:22 · 题解

考虑一些和去年 CSP-S T3 差不多的做法，一个比较 naive 的想法是给每个字符 u 赋一个随机的权值 A_u，并在奇数位上放上 A_u，在偶数位放上 -A_u。用一个区间的权值和是否为 0 来判定，但这样显然会被 \text{abab} 这种搞掉。

问题出在于上述做法中加法没有很好的性质，于是我们考虑用一些没有交换律的运算来搞定这件事，于是我们有了矩阵乘法。

考虑给每个字符 u 赋一个随机矩阵 T_u，并在奇数位放上 T_u，在偶数位放上 T^{-1}_u，其中 T^{-1}_u 为 T_u 的逆，满足 T_u \times T^{-1}_u = I，T^{-1}_u \times T_u = I。不难发现这样很好地解决了上面的问题。

现在相当于查询一个区间的矩阵乘积是否为 I，可以转化为对于一个前缀查询有多少个前缀的矩阵乘积与其相同，这个用哈希搞就行。

以下是一些构造矩阵的方法。

首先就是洛谷矩阵求逆模板题。

假设现在要求大小为 n \times n 的矩阵 A 的逆矩阵，先构造一个 n \times 2n 的矩阵 [AI]，然后对该矩阵进行消元，即将该矩阵左边的 n \times n 的位置变为 I，消元完毕后会得到矩阵 [IA^{-1}]，具体详见模板题解。这种做法强度很好。

但是考场上不一定想得起这玩意，于是下面是一些矩阵的构造。

首先有两个自己是自己的逆的矩阵。

这两个原理一样，但显然下面的矩阵强于上面的矩阵，写上面的矩阵导致 CSP2023-S T2 变为 20pts。下面的矩阵强度足够，你只需要对于每个字符随机两个数 a, b。

下面是两组不自逆的矩阵，在奇数位填上 T，在偶数为填上 T^{-1}。

和

这两种强度都已足够，且上面那种可以手推构造，下面给出倒数第二种的代码以及一道类似的题目。

#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353, maxn = 2e6 + 5, mod2 = 1e9 + 7, pri = 100007, mod3 = 1e9 + 9, mod4 = 2415351;
int n, T;
long long ans;
pair<int, int> has;
char s[maxn];
int ksm(int p, int q) {
    int res = 1;
    while(q) {
        if(q & 1) res = 1ll * res * p % mod;
        p = 1ll * p * p % mod;
        q >>= 1;
    }
    return res;
}
mt19937 rnd(114514229);
struct matrix {
    int a[2][2];
    matrix() {memset(a, 0, sizeof(a));};
    bool operator == (const matrix &rhs) const {
        if(a[0][0] == rhs.a[0][0] && a[0][1] == rhs.a[0][1] && a[1][0] == rhs.a[1][0] && a[1][1] == rhs.a[1][1]) return 1;
        return 0;
    }
    matrix operator * (const matrix &rhs) const {
        matrix res;
        for(int i = 0;i <= 1;i++) {
            for(int j = 0;j <= 1;j++) {
                for(int k = 0;k <= 1;k++) {
                    res.a[i][j] = (res.a[i][j] + 1ll * a[i][k] * rhs.a[k][j]) % mod;
                }
            }
        }
        return res;
    }
}base[maxn];
struct h {
    int tot, pre[maxn], w[maxn], head[2415355];
    matrix id[maxn]; 
    void clear() {
        for(int i = 1;i <= tot;i++) {
            pre[i] = w[i] = head[i] = 0;
            id[i].a[0][0] = id[i].a[0][1] = id[i].a[1][0] = id[i].a[1][1] = 0;
        }
        tot = 0;
    }
    void insert(matrix t) {
        int has1 = 0, tmp = 0;
        for(int i = 0;i <= 1;i++) {
            for(int j = 0;j <= 1;j++) {
                has1 = (1ll * has1 * pri + t.a[i][j]) % mod4;
            }
        }
        tmp = has1;
        ++ tot;
        pre[tot] = head[tmp];
        head[tmp] = tot;
        id[tot] = t;
        w[tot] ++;
    }
    int gethas(matrix t) {
        int has1 = 0, tmp = 0;
        for(int i = 0;i <= 1;i++) {
            for(int j = 0;j <= 1;j++) {
                has1 = (1ll * has1 * pri  + t.a[i][j]) % mod4;
            }
        }
        tmp = has1;
        for(int i = head[tmp];i;i = pre[i]) {
            if(id[i] == t) {
                w[i] ++;
                return w[i] - 1;
            }
        }
        insert(t);
        return 0;
    }
}Has;
int S[maxn];
int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1ll*a*res%mod;
        a=1ll*a*a%mod;b>>=1;
    }return res;
}
int a[30],b[30],c[30],d[30];
void solve() {
    ans = 0;
    cin >> n>>s;
for(int i=1;i<=26;i++){
        a[i]=rnd()%mod;
        c[i]=rnd()%mod;
        d[i]=rnd()%mod;
}
    for(int i = 1;i <= n;i++) {
        int A=c[s[i-1]-'a'+1];
        int B=a[s[i-1]-'a'+1];
        int C=d[s[i-1]-'a'+1];
        if(i&1){
            base[i].a[0][0]=1ll*ksm(A, mod - 2)%mod;
            base[i].a[1][0]=1ll*B * ksm(C,mod-2)%mod * ksm(A, mod - 2) % mod * (mod - 1) % mod;
            base[i].a[0][1]=0;
            base[i].a[1][1]=1ll*ksm(C, mod - 2)%mod;
        }else{
            base[i].a[0][0]=A;
            base[i].a[0][1]=0;
            base[i].a[1][0]=B;
            base[i].a[1][1]=C;
        }
    }
    matrix now;
    now.a[0][0] = now.a[1][1] = 1;
    Has.insert(now);
    for(int i = 1;i <= n;i++){
        now = base[i] * now;
        ans += Has.gethas(now);
    }
    cout << ans;
    Has.clear();
}
int main() {
//  freopen("game.in", "r", stdin);
//  freopen("game.out", "w", stdout);
//  cout << sizeof(Has) / 1024 / 1024 << endl;
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    T = 1;
    while(T --) solve();

}