正题

---

题目大意

$an{s}_i$表示包含字符$i$的括号匹配子串个数

求$$\sum _{i=1}^n(an{s}_i\ast i\mathrm{m}\mathrm{o}\mathrm{d}(1e9+7))$$

---

解题思路

计算出每个匹配括号的前一个括号位置和后一个括号位置。
一个差分数组
先计算加的，其实对于每一些同级括号，差分数组就按顺序从1到$k$（k表示括号个数）
减的同理
举个例子

$s$$($$)$$($$)$$end$

$add$	1	0	2	0	0
$reduce$	0	0	1	0	2

---

$code$

#include<cstdio> #include<algorithm> #include<cstring> #include<stack> #define ll long long using namespace std; const ll XJQ=1e9+7,N=1e6+10; char s[N]; stack<int> ss; ll n,t,last[N],next[N],r[N],l[N],sum[N],ans; int main() {scanf("%lld",&t);while(t--){scanf("%s",s+1);ans=0;memset(l,0,sizeof(l));memset(r,0,sizeof(r));memset(last,0,sizeof(last));memset(next,0,sizeof(next));memset(sum,0,sizeof(sum));while(!ss.empty()) ss.pop();n=strlen(s+1);for(ll i=1;i<=n;i++)if(s[i]=='(') ss.push(i);else if(!ss.empty()){last[i+1]=ss.top();next[ss.top()]=i+1;ss.pop();}for(ll i=n+1;i>=1;i--){r[i]++;r[last[i]]+=r[i];}for(ll i=0;i<=n;i++){l[i]--;l[next[i]]+=l[i];}for(ll i=1;i<=n;i++)sum[i]=sum[i-1]+l[i]+r[i],ans+=sum[i]*i%XJQ;printf("%lld\n",ans);} }

总结

以上是生活随笔为你收集整理的jzoj4209-已经没有什么好害怕的了【差分】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。