問題描述

Sereja在平面上畫了n個(gè)點(diǎn)，點(diǎn)i在坐標(biāo)(i,0)。然后，Sereja給每個(gè)點(diǎn)標(biāo)上了一個(gè)小寫或大寫英文字母。Sereja不喜歡字母"x"，所以他不用它標(biāo)記點(diǎn)。Sereja認(rèn)為這些點(diǎn)是漂亮的，當(dāng)且僅當(dāng)：
　　·所有的點(diǎn)可以被分成若干對(duì)，使得每個(gè)點(diǎn)恰好屬于一一對(duì)之中。
　　·在每對(duì)點(diǎn)中，橫坐標(biāo)較小的會(huì)被標(biāo)上小寫字母，較大的會(huì)被標(biāo)上對(duì)應(yīng)的大寫字母。
　　·如果我們?cè)诿繉?duì)點(diǎn)上畫一個(gè)正方形，其中已知的一對(duì)點(diǎn)會(huì)作為正方形的相對(duì)的頂點(diǎn)，它們間的線段會(huì)成為正方形的對(duì)角線，那么在所有畫出的正方形中不會(huì)有相交或觸碰的情況。
　　小Petya擦掉了一些小寫字母和所有大寫字母，現(xiàn)在Sereja想知道有多少種方法來還原每個(gè)點(diǎn)上的字母，使得還原后這些點(diǎn)是漂亮的。
輸入格式
　　第一行是一個(gè)整數(shù)n，表示點(diǎn)的個(gè)數(shù)。
　　第二行是一個(gè)長(zhǎng)度為n的字符串，包含小寫字母和問號(hào)"?"，是按照橫坐標(biāo)遞增的順序的每個(gè)點(diǎn)的描述。問號(hào)表示這個(gè)點(diǎn)的字母被Petya擦掉了。保證輸入串不含字母"x"。

輸出格式

輸出答案對(duì)4294967296取模的值。如果沒有可行的方案，輸出0。

樣例輸入

4
a???

樣例輸出

50

樣例輸入

4
abc?

樣例輸出

0

樣例輸入

6
abc???
樣例輸出
1

數(shù)據(jù)規(guī)模和約定

20個(gè)測(cè)試點(diǎn)的n分別為：
5,10,20,50,100,
200,500,1000,2000,5000,
10000,20000,30000,40000,50000,
60000,70000,80000,90000,100000.

代碼如下

#include <iostream>
#include<algorithm>
#include<cstring>
//這題的重點(diǎn)還在于“輸出答案對(duì)4294967296取模的值”
//所以用unsigned int
#define LL unsigned int
using namespace std;

//這道題是我最開始想得復(fù)雜了
//又或是說沒有看清楚題目，罪過罪過
//我們只需要算出需要填小寫字母的問號(hào)位置和需要填大寫字母的問號(hào)位置就可以了
//設(shè)小寫字母問號(hào)位置有p個(gè)
//大寫字母問好位置有q個(gè)
//最后就有25*p+q種

int n,p;//p是用來記錄小寫字母的個(gè)數(shù)
char c[200010];
LL f[200010]={1};
LL sum=1;

int main()
{
    cin>>n;
    cin>>c+1;
    if(n&1)
        cout<<"0"<<endl;
    else{
        int m=n>>1;//除以2
        for(int i=1;i<=n;i++){
            if(c[i]=='?'){
                //這里最后要用到的是f[m]
                //因?yàn)樽詈罄塾?jì)到了中間的數(shù)
                for(int j=i>>1;j>=i-m&&j;j--){
                    f[j]+=f[j-1];
                }
            }else{
                p++;//這是已經(jīng)存在的小寫字母
            }
        }
        //計(jì)算問號(hào)的小寫字母
        for(int i=1;i<=m-p;i++)
            sum*=25;
        sum*=f[m];
        cout<<(LL)sum<<endl;
    }

    return 0;
}