Best Parenthesis

一.题意

给定一个串，0代表‘('，1代表')'
‘()’代表一分，‘()()’这样代表1 + 1分，‘(())’这样是2 * 1分，计算给定串的分数对12345678910取模。

二.分析

可以发现((())) -- 每一个左括号代表2的0次方，2的1次方，2的2次方依次递增,cnt++，且只有当遇到s[i-1] == '(' && s[i] == ')'的时候才计算数值，否则遇到')'就只cnt--

例如：s('(())()') = s('(())') + s('()') = 2的1次方 + 1 = 3；
s('((())())') = s('((()))') + s('(())') = 2的2次方 + 2的1次方 = 6；

所以问题就转化为根据左右括号求2的次方，因为模数 > 1e9，所以在快速幂的基础上还要加上防爆；

三.代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const ll mod = 12345678910;

ll n,cnt,a[maxn],ans;

ll mul(ll x,ll n){
    ll ans = 0;
    while(n){
        if(n&1) ans = (ans + x) % mod;
        x = x * 2 % mod;
        n >>= 1;
    }
    return ans;
}

ll m_pow(ll x,int n){
    ll res = 1;
    while(n){
        if(n&1)    res = mul(res,x);
        x = mul(x,x);
        n >>= 1;
    }
    return res % mod;
}

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        if(a[i] == 0)    cnt++;
        else{
            cnt--;    //因为每个左括号都要加一次，所以每遇到')'都会自减
            if(a[i-1] == 0){
                ll k = m_pow(2,cnt);
                ans = (ans + k) % mod;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}