Solution

我觉得难度没有题解里面说的 *2400 , 大概 *2200 的样子 ?

这个括号序列权值可以看做一个函数 $f (l, r)$ , 表示 $[l, r]$ 区间内括号串的权值 . 答案就让我们求 $\sum_{l=1}^n \sum_{r=l}^n f(l,r)$ .

对于这种奇怪的函数求和 , 我们首先要考虑如何计算 $f (l, r)$ . 贪心地 , 我们处理的肯定是最靠右的 () , 这样后面的右括号会尽可能少 . 因此 , 我们可以断言 , 此时我们选取的括号对后面只有右括号 . 考虑把 ) 当做 $1$ , 把 ( 当做 $- 1$ . 那么我们删掉一个括号对 , 其右边所有的 ( 肯定已经和另外一个 ) 消掉了 , 宏观上表现为他们和为 $0$ . 所以删除一个括号对的代价其实就是右边所有 $\pm 1$ 序列的和 .

然后再考虑如何找到所有的合法括号序列 . 显然一个合法的括号序列可以写成 (...)(...)(...) 的形式 , 所以枚举括号序列的最左端 , 我们只需要找到第一个独立的 (...) 形态的括号序列 .

显然要求 $S_{l} = ($ . 设转化后 $\pm 1$ 序列的前缀和为 $p r e$ . 然后由经典结论 : 右端点是第一个 $r$ 使得 $r > l$ 且 $pre_r = pre_{l-1}$ . 这样我们就可以找到这个独立的单元了 .

然后所有以 $l$ 开头的合法括号序列都是 (...) , (...)(...) , (...)(...)(...) 这样的 . 这种并联的括号序列肯定要从右往左逐个击破 , 他们是独立的 . 所以当我们找到极长的括号序列 (...)(...)(...)...(...) 后 , 最左边的要记录 $1$ 次贡献 , 然后依次是 $2$ 次 , $3$ 次 ......

最后就是一堆前缀和与后缀和 .

写的有点抽象 , 可以参考代码 .

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=3e5+10,MOD=1e9+7;
int n,ans,pre[MAXN],fans[MAXN],val[MAXN],suf[MAXN],cst[MAXN],cnt[MAXN],fst[MAXN]; //fst represents the first right pos that make (i,fst) a correct bracket sequence
map<int,int> lst;
string S;
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>S; n=S.size(),S="&"+S;
    ffor(i,1,n) if(S[i]=='(') pre[i]=pre[i-1]+1; else pre[i]=pre[i-1]-1;
    roff(i,n,1) if(S[i]==')') suf[i]=suf[i+1]+1; else suf[i]=suf[i+1]-1;
    roff(i,n,1) {
        val[i]=val[i+1];
        if(S[i]==')') val[i]=(val[i]+suf[i+1])%MOD;
    }
    roff(i,n,1) {
        if(S[i]==')') fst[i]=-1;
        else if(!lst.count(pre[i-1])) fst[i]=-1;
        else fst[i]=lst[pre[i-1]];
        lst[pre[i]]=i;
    }
    roff(i,n,1) if(fst[i]!=-1) {
        cst[i]=val[i]-val[fst[i]+1]-(fst[i]-i+1)/2*suf[fst[i]+1];
        cnt[i]=cnt[fst[i]+1]+1;
        fans[i]=(fans[fst[i]+1]+cnt[i]*cst[i])%MOD;
        ans=(ans+fans[i])%MOD;
    }
    ans=(ans+MOD)%MOD;
    cout<<ans;
    return 0;
}

变量解释 :

pre : $\pm 1$ 序列前缀和 . suf : 后缀和 .
val : 对于每个右括号 , 求出右边所有 $\pm 1$ 序列的后缀和 , 再对这个东西求后缀和 .
fst ( 多么吉利的名字 ) : 最小的 (...) 单元的右端点 .
cst : 消除一个独立小单元的代价 .
cnt : 极长括号序列的独立小单元数 .
fans : 以某一点开头的所有括号序列的答案 .

题解 | #小红的括号串权值#

Solution