题目地址：Codeforces：Problem – 314E – Codeforces、洛谷：【CF314E】Sereja and Squares – 洛谷

题目描述

Sereja painted n points on the plane, point number i (1 ≤ i ≤ n) has coordinates (i, 0). Then Sereja marked each point with a small or large English letter. Sereja don’t like letter “x”, so he didn’t use it to mark points. Sereja thinks that the points are marked beautifully if the following conditions holds:

• all points can be divided into pairs so that each point will belong to exactly one pair;
• in each pair the point with the lesser abscissa will be marked with a small English letter and the point with the larger abscissa will be marked with the same large English letter;
• if we built a square on each pair, the pair’s points will be the square’s opposite points and the segment between them will be the square’s diagonal, then among the resulting squares there won’t be any intersecting or touching ones.

Little Petya erased some small and all large letters marking the points. Now Sereja wonders how many ways are there to return the removed letters so that the points were marked beautifully.
本来有一个由大小写字母组成的序列，序列满足以下条件：

• 大小写字母两两都配对，配对指同一字母的大小写配对，且小写字母在左侧
• 不能发现穿插的情况，例如abAB是不合法的，应该调整为aAbB或abBA

现在所有的大写字母和部分小写字母被擦掉了，求恢复为一个满足上述序列的可行情况数量。

输入输出格式

输入格式：
The first line contains integer n the number of points (1 ≤ n ≤ 105). The second line contains a sequence consisting of n small English letters and question marks — the sequence of letters, that mark points, in order of increasing x-coordinate of points. Question marks denote the points without letters (Petya erased them). It is guaranteed that the input string doesn’t contain letter “x”.

输出格式：
In a single line print the answer to the problem modulo 4294967296. If there is no way to return the removed letters, print number 0.
Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入样例#1：

4
a???

输出样例#1：

20

输入样例#2：

4
abc?

输出样例#2：

0

输入样例#3：

6
abc???

输出样例#3：

1

题解

首先我们可以把小写字母看成左括号，大写字母看成右括号，这样就变成了求一个合法的括号序列的问题了。我们考虑使用动态规划。
令dp[i][j]表示处理到第i个字符，到现在还有j个左括号没有配对。分类转移：
如果i+1是左括号，把当前值加到dp[i+1][j+1]上。
如果i+1是问号，把当前值加到dp[i+1][j-1]（如果i+1是右括号）和dp[i+1][j+1]（如果i+1是左括号）上。
最后的答案就是dp[n][0]。
但是这么做的时间复杂度是O(n^2)的。因为i和j的上限都是n。

我们尝试换一种思路，用dp[i][j]表示处理到前i个，里面有j个右括号。只需要转移当前是问号的情况，填左括号dp[i][j]+=dp[i-1][j]，填右括号dp[i][j]+=dp[i-1][j-1]。
最后的答案是dp[n][n/2]。
相比前一种想法，在这种想法中里面那层循环的规模会减小很多，这个可以感性的认识一下，因此我们大幅减小了常数，这个题就能过了。

等等，还没完！原题说用[a-wy-z]这个字符集里面的字母当做左括号来着，那么我们还要乘上25^{\frac{n}{2}-q}这个数字。q是题目固定的小写字母数量。因为每个左括号都可以有25种选择，右括号又是已经配对好的。到这里这个题就做完了。
对于取模，我们发现4294967296 = 2^{32}，可以使用unsigned int的自然溢出来减小取模的常数。

代码

// Code by KSkun, 2018/3
#include <cstdio>

// variables

const int MAXN = 100005;

int n;
char str[MAXN];
unsigned int dp[MAXN];

// main

int main() {
    scanf("%d%s", &n, str + 1);
    if(n & 1) {
        printf("0");
        return 0;
    }
    dp[0] = 1;
    int cntl = 0, hn = n / 2;
    for(int i = 1; i <= n; i++) {
        if(str[i] == '?') {
            for(int j = i / 2; j && j >= i - hn; j--) {
                dp[j] += dp[j - 1];
            }
        } else {
            cntl++;
        }
    }
    unsigned int ans = dp[hn];
    for(int i = 1; i <= hn - cntl; i++) {
        ans *= 25;
    }
    printf("%u", ans);
    return 0;
}