题目描述

资源限制
时间限制：4.0s 内存限制：256.0MB
问题描述
　　Sereja在平面上画了n个点，点i在坐标(i,0)。然后，Sereja给每个点标上了一个小写或大写英文字母。Sereja不喜欢 字母”x”，所以他不用它标记点。Sereja认为这些点是漂亮的，当且仅当：
　　·所有的点可以被分成若干对，使得每个点恰好属于一一对之中。
　　·在每对点中，横坐标较小的会被标上小写字母，较大的会被标上对应的大写字母。
　　·如果我们在每对点上画一个正方形，其中已知的一对点会作为正方形的相对的顶点，它们间的线段会成为正方形的对 角线，那么在所有画出的正方形中不会有相交或触碰的情况。
　　小Petya擦掉了一些小写字母和所有大写字母，现在Sereja想知道有多少种方法来还原每个点上的字母，使得还原后这 些点是漂亮的。
输入格式
　　第一行是一个整数n，表示点的个数。
　　第二行是一个长度为n的字符串，包含小写字母和问号”?”，是按照横坐标递增的顺序的每个点的描述。问号表示这个点的字母被Petya擦掉了。保证输入串不含字母”x”。
输出格式
　　输出答案对4294967296取模的值。如果没有可行的方案，输出0。

数据规模和约定
　　20个测试点的n分别为：
　　5,10,20,50,100,
　　200,500,1000,2000,5000,
　　10000,20000,30000,40000,50000,
　　60000,70000,80000,90000,100000.

样例

样例输入

4
a???

样例输出

50

样例输入

4
abc?

样例输出

0

样例输入

6
abc???

样例输出

1

C++ 代码

#include<stdio.h>
#define max(a,b)  a>b?a:b
typedef  unsigned int love;
const int N = 1e5 + 7;
//4294967296==2^32-1,4294967296是unsign int 的溢出值，对其取模就是它的自然溢出，所以不必取模
//题意要求：
//不能出现取两对点的下标分别为 a,b,c,d(a，b 一对，c，d一对)
//则它们要满足( a < b < c < d )或者( a < c < d < b)
char tmp[N];
love ali[N];//下标N表示的是确定了N个右括号，使用滚动数组
int n;

int main(void)
{
    scanf("%d", &n);
    scanf("%s", tmp + 1);
    if (n & 1)return putchar('0'), 0;//奇偶校验，若为奇数则不可能有满足题意的解
    ali[0] = 1;//无右括号出现
    int left = 0, n2 = n >> 1;//left统计左括号的个数，如果超过一半则不满足题意

    for (int idx = 1; idx <= n; idx++)
        if ('?' == tmp[idx])
        {
            int kj = idx >> 1;//确定右括号最大上限
            //当dp到下标idx时，可以确定的最多的右括号为idx/2，
            //若现在确定的是左括号则前面idx-1个格子就是确定kj个右括号的结果
            //若现在确定的是右括号，则前面idx-1个格子确定的就是kj-1个右括号的结果
            if (idx != n)for (; kj >= 1; kj--)ali[kj] += ali[kj - 1];
            else ali[kj] = ali[kj - 1];
            //i==n一定是右括号，只要确定前n-1个格子所确定出来的n>>1-1个右括号的结果即可
        }
        else left++;//若这一定是左括号的结果
                    //记录左括号个数

    if (left > n2)return putchar('0'), 0;
    else for (int i = 0; i < n2 - left; i++)ali[n2] *= 25;
    //还有多少个左括号没有确定左括号有25种，一种没确定答案就翻25倍


    printf("%u", ali[n2]);
    return 0;
}