P2532 [AHOI2012]树屋阶梯

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

题意

N个阶梯，用N个矩阵有多少种摆放方式组合成。

思路

因为，N个梯阶最少需要N个矩形，所以我们摆放的时候，肯定要贪心一下。
考虑下面的梯阶，红色矩形必须包括在某个矩形内部。

因为只能用N个矩形，所以包含这个红色矩形只能是下面四种颜色框起来的部分。

其他部分就在除框起来部分之外找了。
比如蓝色框框：

代码

#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;
const ll mod = 1e8+7;
using namespace std;

int N;
string f[maxn];
string mul(string a,ll b){
    string c = "";
    ll t = 0;
    for(int i = a.size()-1;i>=0 || t;i--){
        if(i>=0) t += (a[i]-'0')*b;
        c += (t%10) +'0';
        t/=10;
    }
    reverse(c.begin(),c.end());
    return c;
}
string div(string a,ll b){
    string c = "";
    ll cur = 0;
    for(int i = 0;i<a.size();i++){
        cur = cur*10 + (a[i]-'0');
        c += to_string(cur/b);
        cur %= b;
    }
    int idx = c.find_first_not_of('0');
    return idx!=-1 ? c.substr(idx) : "0";
}
int main(){
    ios;
    cin>>N;
    f[0] ="1";f[1] = "1";
    for(int i = 2;i<=N;i++){
        f[i] = div(mul(f[i-1],(4*i-2)),i+1);
    }
    cout<<f[N]<<'\n';
    return 0;
}