Tác giả: skyvn97

Xem: https://www.youtube.com/live/qWz664WCmJw?si=mX9ZCtS6Ry5dFNqq

#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define fi   first
#define se   second
#define MASK(i) (1LL<<(i))
#define BIT(x,i) (((x)>>(i))&1)
#define div   ___div
#define next   ___next
#define prev   ___prev
#define left   ___left
#define right   ___right
#define __builtin_popcount __builtin_popcountll
using namespace std;
template<class X,class Y>
    void minimize(X &x,const Y &y) {
        if (x>y) x=y;
    }
template<class X,class Y>
    void maximize(X &x,const Y &y) {
        if (x<y) x=y;
    }
template<class T>
    T Abs(const T &x) {
        return (x<0?-x:x);
    }

/* Author: Van Hanh Pham */

/** END OF TEMPLATE - ACTUAL SOLUTION COMES HERE **/

#define MAX   666
const int MOD = (int)1e9 + 22071997;

int f[MAX][MAX], sum[MAX][MAX], n;
bool ok[MAX][MAX];
char input[MAX];

void init(void) {
    scanf("%d", &n);
    FOR(i, 1, n - 1) {
        scanf("%s", input + 1);
        FOR(j, 1, n - i) {
            ok[i][i + j] = input[j] == 'Y';
            ok[i + j][i] = input[j] == 'N';
        }
    }
}

void process(void) {
    FOR(i, 1, n) f[i][i] = 1;
    FOR(i, 1, n - 1) {
        sum[i][i + 1] = 1;
        f[i][i + 1] = ok[i][i + 1] ? 1 : 0;
    }

    FOR(d, 2, n) FOR(l, 1, n - d) {
        int r = l + d;
        FOR(i, l + 1, r) sum[l][r] = (sum[l][r] + 1LL * f[l][i - 1] * f[i][r]) % MOD;

        FOR(i, l + 1, r) if (f[i][r] > 0 && ok[l][i])
            f[l][r] = (f[l][r] + 1LL * sum[l][i] * f[i][r]) % MOD;
    }

    printf("%d\n", f[1][n]);
}

int main(void) {
#ifdef ONLINE_JUDGE
    freopen("drawatree.inp", "r", stdin);
    freopen("drawatree.out", "w", stdout);
#endif // ONLINE_JUDGE

    init();
    process();
    return 0;
}

/*** LOOK AT MY CODE. MY CODE IS AMAZING :D ***/