xdu 1166 - 括号，又见括号

1166 - 括号，又见括号

  

    经典的括号题，

    wiki里写的没有看懂，但貌似是基于全局的。

    我觉得这道题前面的括号和后面的并没有关系，所以从全局找到每一对匹配并不是最好的选择，直接进行匹配反而更简单

    用getchar时间比scanf少了一半……

   注意一下输出要是long long的，一开始没发现用int，WA了好几次。

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <cstdio>
#define INF 12345678910ll
int n;
char t;
void get(char &t){t=getchar(),getchar(),n--;}
long long dfs()
{
    long long ans=0;
    for(get(t);t=='0';get(t))
       ans=(ans+dfs())%INF;
    if(ans==0)return 1;
    else return ans<<1;
}
int main()
{
    while(~scanf("%d%*c",&n))
    {
        long long ans=0;
        while(n--)
        {
            getchar();getchar();
            ans=(ans+dfs())%INF;
        }
        printf("%lld\n",ans);
    }
    return 0;
}