思路

根据赛时的检验,
典型的动点问题的 \(\rm{trick}\) 并不能在这里使用, 也就是说, 分类讨论

• 前缀 + \(i\) + 后缀
• 前缀 + \(i\)
• 后缀 + \(i\)

是不可行的

考虑括号串问题的常见做法, 先将其赋值成 \(1, -1\) 之后进行处理
你发现这种做法有枚举字段和的瓶颈, 所以也不可行
当然你可以进行转化之后利用这种做法

用栈来处理更是天方夜谭

考虑转到图上去处理, 容易的, 你可以将一个合法括号串表示成这样

你发现令 \(f_i\) 表示 \(i\) 节点的答案, 容易有

其中 \(lb, rb\) 表示左右兄弟的个数

容易转移

考虑建树怎么建
你发现不用真的建树, 你只需要把 \(lb, rb\) 求出来即可, 而这个你只需要在原串上直接做即可

实现

框架

如上维护

代码

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

const int MAXN = 10000010, mod = 1e9 + 7;
int n, to[MAXN], stk[MAXN], tp, ans[MAXN], rans[MAXN]; ll res;
char s[MAXN];
int pre[MAXN];

signed main () {
	scanf("%s", s + 1), n = strlen (s + 1);
	for (int i = 1; i <= n; i++) {
		if (s[i] == '(') stk[++tp] = i;
		else if (tp) {
            to[stk[tp]] = i, to[i] = stk[tp], tp--;
            if (tp) pre[to[i]] = stk[tp];
        }
	}
	for (int i = n; i >= 1; i--) if (to[i]) {
		if (s[i] == '(') ans[i] = ans[to[i] + 1] + 1;
	}
	for (int i = 1; i <= n; i++) if (to[i]) {
		if (s[i] == ')') rans[i] = rans[to[i] - 1] + 1;
	}
	for (int i = 1; i <= n; i++) if (to[i]) {
		if (s[i] == '(') { ans[i] = ans[to[i]] = ans[pre[i]] + 1ll * ans[i] * rans[to[i]] % mod; }
		res += (1ll * i * ans[i]) % mod;
	}
	printf("%lld", res);
	return 0;
}

总结

想的其实挺有逻辑的, 但是确实不会这种情况下的问题

常用的方法, 把匹配类问题丢到图 / 树上去做
本质上其实是因为这个题中, 包含关系的括号串对答案是有继承关系的, 这种继承关系可以建成树来处理

不好建树考虑只利用思想, 简化计算