一.题意
给定一个串,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; }