UVALive 3516Exploring Pyramids

제목: 문자열 S를 지정합니다. 이 s열은 나무의 dfs 순서입니다.dfs 서열이 s인 나무에 몇 가지 상황이 있는지 구합니다.

분석: 수학 기초 예제 4.

코드:

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<math.h>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int N=2000010;
const int MAX=151;
const int MOD1=1000007;
const int MOD2=100000009;
const double EPS=0.00000001;
typedef long long ll;
const ll MOD=1000000000;
const ll INF=10000000010;
typedef unsigned long long ull;
char s[310];
ll dp[310][310];
int main()
{
    int i,j,k,len;
    while (scanf("%s", s)!=EOF) {
        len=strlen(s);
        if (!(len&1)) { printf("0
");continue ; }
        memset(dp,0,sizeof(dp));
        for (i=1;i<=len;i++) dp[i][i]=1;
        for (i=3;i<=len;i+=2)
            for (j=1;j<=len-i+1;j++)
            if (s[j-1]==s[j+i-2]) {
                for (k=j+2;k<=j+i-1;k+=2)
                if (s[j-1]==s[k-1]) dp[j][j+i-1]=(dp[j][j+i-1]+dp[j+1][k-1]*dp[k][j+i-1])%MOD;
            }
        printf("%lld
", (dp[1][len]+MOD)%MOD);
    }
    return 0;
}