C++(g++ 7.5.0) 解法, 执行用时: 33ms, 内存消耗: 26492K, 提交时间: 2023-07-07 21:14:15

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
const int N = 3e5 + 10, P = 1e9 + 7;

string s;

vector<int> g[N];

int n, sz[N];
i64 ans[N], tot;



void dfs(int u) {
    sz[u] = 1;
    for(int v : g[u]) {
        dfs(v);
        sz[u] += sz[v];
        ans[u] += sz[v] + ans[v];
        ans[u] %= P;
    }
    
    for(int i = 0; i < g[u].size(); i ++) {
        int v = g[u][i];
        tot += ans[v] * (i + 1ll) * (g[u].size() - i) % P;
        tot %= P;
    }
}

void solve() {
    cin >> s;
    vector<int> stk(1, 0);
    for(char c : s) {
        if(c == '(') {
            g[stk.back()].push_back(++ n);
            stk.push_back(n);
        }else {
            stk.pop_back();
            if(stk.empty())
                stk.push_back(++ n);
        }
    }
    for(int i = 1; i < stk.size(); i ++) {
        g[stk[i - 1]].pop_back();
    }
    for(int u = 0; u <= n; u ++) {
        if(!sz[u]) dfs(u);
    }
    cout << tot;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    solve();
}

C++(clang++ 11.0.1) 解法, 执行用时: 13ms, 内存消耗: 3304K, 提交时间: 2023-07-08 14:50:14

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int mod=1e9+7;
char s[N];
int q[N],pos[N];
int tot;
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	long long ans=0;
	for (int i=1;i<=n;i++) if (s[i]=='('){
		pos[++tot]=i;
		q[tot]=-1;
	}else{
		vector<int>w;
		int s=0;
		while (tot&&q[tot]!=-1){
			w.push_back(q[tot]);
			s=(s+q[tot])%mod;
			tot--;
		}
		for (int j=0;j<w.size();j++) ans=(ans+1ll*(j+1)*((int)w.size()-j)%mod*w[j]%mod)%mod;
		if (tot){
			q[tot]=(s+(i-pos[tot])/2)%mod;
		}
	}
	for (int i=1;i<=tot;i++) 
		if (q[i]>=0){
			int j=i; 
			vector<int>w;
			w.push_back(q[i]);
			while (j<tot&&q[j+1]>=0){
				j++;
				w.push_back(q[j]);
			}
			i=j;
			for (int j=0;j<w.size();j++) ans=(ans+1ll*(j+1)*((int)w.size()-j)%mod*w[j]%mod)%mod;
		}
	printf("%d\n",ans);
}