题解——括号序列（栈）

可以猜到,ssw02爆0了

ssw02要怼一下 Y - - ，数据和标程都是反的，题还换错了一道，T2做了一半换题意,S----,emmm

题面

题目出现了九条老师..... 然后发现一句经典，不要先开题面 有九条、我妻、.....

输入 就是一行字符串了

输出 就是方案数了

思路

我们先用栈来判断是否合法，想着骗分，然后

咦？这个东西，可以简化吧。

然后我们发现 ， 在 n^2 暴力枚举的基础上，可以优化 。

具体而言，就是 ， 如果存在一种合法区间[ L , R ]，那么一定会导致 L-1 时刻 和 R+1 时刻的栈完全相同 。

然后我们发现，这样相同的栈就像端口一样，可以相互搭配 。

就是如果有 K 个相同的端口 , 就有 K*( K-1 )/2 的贡献方案 ,至于比较 ，Hash一下就好了

顺便一提，可以记录之前的状态，在出栈时直接把hash值赋为历史值即可避免出栈时无法连续Hash的问题。

然后 ， ssw02惊奇地发现 ， 题目变水了

代码

#include<bits/stdc++.h>
using namespace std ;
#define ull unsigned long long
const int MAXN = 100005 , BASE = 1007 , mod = 998244353 ;
int a[ MAXN ] , st[ MAXN ],  N ;
ull num[ MAXN ] , top[ MAXN ]; 
char g[ MAXN ] ;
int main(){
    freopen("B.in","r",stdin);
    freopen("B.out","w",stdout);
    scanf("%s",g); N = strlen(g) ;
    for( register int i = 1 ; i <= N ; ++i )
        a[ i ] = ( int )( g[ i-1 ]+1 ) ;
    int head = 0 ; 
    for( register int i = 1 ; i <= N ; ++i ){
        if( a[ i ] == st[ head ] ){ head-- ; continue ; }
        else st[ ++head ] = a[ i ] ;
    }
    if( head ){cout<<"0";return 0;}
    for( register int i = 1 ; i <= N ; ++i ){
        if( a[ i ] == st[ head ] ){
            num[ i ] = num[ top[ --head ] ] ;
            continue ;
        }
        st[ ++head ] = a[ i ] ;
        top[ head ] = i ;
        num[ i ] = (ull)num[ i-1 ]*BASE + (ull)a[ i ] ;
    }
    //for( register int i = 1 ; i <= N ; ++i )cout<<num[ i ]<<" " ;
    sort( num+1 , num+N+1 ) ;
    ull ans = 0 ; ull l = 0 , r = 0 ;
    while( r <= N ){
        l = r ;
        while( num[ l ] == num[ r ] && r <= N )
        r++ ;
        ans = ( ans+(r-l)*(r-l-1)/2 ) %mod ;
    }
    cout<<ans ;
    return 0 ;
}

题解——括号序列(栈)

原文：https://www.cnblogs.com/ssw02/p/11628298.html