CF1223F Stack Exterminable Arrays

题面

简化题意

定义一个序列是好的，当且仅当将其元素从左到有入栈，若栈顶两个元素相同则消掉，最终栈为空的序列。

给定一个序列，求它有多少个子串是好的。

$n\leq 3\times 10^5$。

题解

我们考虑到这样一件事情：显然一个好的序列至少要有一对数字是相邻的，否则完全消不掉任何数字。这时，我们先把这两个数字消掉，再消其它的数字，结果是不变的。

换句话说，这个“消除”的方式满足结合律——在序列上添加一些“括号”，先消除“括号”里面的数字，直到“括号”里的数字消完之后，再从左往右消除，结果是不变的。

我们还知道一个东西，它的运算也满足结合律：矩阵乘法。

对于 $1\sim n$ 中的所有数，给每个数字 $i$ 随机赋权为一个矩阵 $F_i$。然后把矩阵对应在输入的序列上：对于一个数字 $x$，若 $x$ 是第奇数次出现，则赋为 $F_x$，否则将其赋为 $F_x$ 的逆矩阵（不妨设为 $G_x$），得到一个矩阵序列。

那么判定一个子串是好的，可以转化为判定这个子串所有矩阵的积为单位矩阵 $\epsilon$。

于是你对矩阵序列作前缀积，记为序列 $S$，不难发现如果一段子串 $[l,r]$ 的积为单位矩阵，则 $S_r \div S_{l-1} = \epsilon$，则说明 $S_r = S_{l-1}$。（此处的除法表示乘上除数的逆元。）

于是开个 map 记录一下每个前缀积的出现次数即可。

说句题外话，如果把数字改成括号序列，每次把栈顶匹配的左右括号删除的话，就不能用这种方法做了。因为 $F_x \times G_x = G_x \times F_x = \epsilon$，但是只有 () 这样的括号串才合法，)( 这样的括号串并不合法。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int max_n=300005,mod=1000000009;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
inline int mi(int a,int p=mod-2){
    int res=1;
    while(p){
        if(p&1) res=res*a%mod;
        a=a*a%mod,p>>=1;
    }
    return res;
}
struct Matrix{
    int f[2][2];
    Matrix(int A=0,int B=0,int C=0,int D=0){
        f[0][0]=A,f[0][1]=B,f[1][0]=C,f[1][1]=D;
    }
    Matrix operator * (Matrix &b){
        Matrix a=*this;
        return Matrix((a.f[0][0]*b.f[0][0]+a.f[0][1]*b.f[1][0])%mod,(a.f[0][0]*b.f[0][1]+a.f[0][1]*b.f[1][1])%mod,(a.f[1][0]*b.f[0][0]+a.f[1][1]*b.f[1][0])%mod,(a.f[1][0]*b.f[0][1]+a.f[1][1]*b.f[1][1])%mod);
    }
    bool operator < (const Matrix &b) const{
        Matrix a=*this;
        if(a.f[0][0]^b.f[0][0]) return a.f[0][0]<b.f[0][0];
        if(a.f[0][1]^b.f[0][1]) return a.f[0][1]<b.f[0][1];
        if(a.f[1][0]^b.f[1][0]) return a.f[1][0]<b.f[1][0];
        if(a.f[1][1]^b.f[1][1]) return a.f[1][1]<b.f[1][1];
        return 0;
    }
    bool operator == (const Matrix &b) const{
        Matrix a=*this;
        return (a.f[0][0]==b.f[0][0] && a.f[0][1]==b.f[0][1] && a.f[1][0]==b.f[1][0] && a.f[1][1]==b.f[1][1]);
    }
}f[2][max_n],S;
const Matrix Ep(1,0,0,1);
inline Matrix Inv(Matrix a){
    int x=mi((a.f[0][0]*a.f[1][1]-a.f[1][0]*a.f[0][1]%mod+mod)%mod);
    return Matrix(a.f[1][1]*x%mod,mod-a.f[0][1]*x%mod,mod-a.f[1][0]*x%mod,a.f[0][0]*x%mod);
}

map<Matrix,int> mp;

int n,cnt[max_n],ans;
const int N=300000;

signed main(){
    srand(time(0));
    for(int i=1;i<=N;++i){
        f[1][i]=Matrix(rand()%mod,rand()%mod,rand()%mod,rand()%mod);
        f[0][i]=Inv(f[1][i]);
    }
    for(int T=read();T;--T){
        n=read();
        S=Ep,ans=0;
        mp.clear(),++mp[Ep];
        for(int i=1;i<=n;++i){
            int x=read();
            ++cnt[x];
            S=S*f[cnt[x]&1][x];
            ans+=mp[S]++;
        }
        write(ans),putchar('\n');
        memset(cnt,0,sizeof(int)*(n+1));
    }
    return 0;
}