P1722 矩阵 II

题目链接：https://www.luogu.com.cn/problem/P1722

思路

首先题目有一点说漏了。总的红色要等于总的黑色数量
我们只要把放棋子看成是入栈和出栈就可以了。为啥？因为题目说无论什么时候的i，都要1~i的红大于黑，而任何时候的入栈数量肯定是大于出栈数量的。

代码

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int N;
ll f[maxn];
int main(){
    // debug;
    ios;
    cin>>N;
    f[0] = 1;f[1] = 1;
    for(int i = 2;i<=N;i++){
        for(int j = 0;j<=i-1;j++){
            f[i] = (f[i] + f[j] * f[i-1-j])%100;
        }
    }
    cout<<f[N]<<'\n';
    return 0;
}