「2019-08-13 省常中互测」蛋糕

Description

每次对一个蛋糕可以横竖切一刀,最后变成$1\times 1$的小块,问有多少种本质不同的切法。

答案对$10^9+7$取模。

Data Range

$n,m\leq 300$

Solution

$f[i][j]$表示大小为$i\times j$的方块的切法。

状态转移方程就是枚举$k$表示我们现在切的行数和列数。

边界值为$f[1][1]=1$

笔者采用记忆化搜索的写法。

Code

#include <bits/stdc++.h>

using namespace std;

const int P = 1000000007;

template <typename T> void pls(T &x, T y) {
    x = x + y >= P ? x + y - P : x + y;
}

template <typename T> T mul(T x, T y) {
    return (long long) x * y % P;
}

const int N = 305;
int n, m;
int f[N][N];

int dfs(int n, int m) {
    if (f[n][m] != -1) return f[n][m];
    int &res = f[n][m];
    res = 0;
    for (int i = 1; i <= n; i ++) {
        pls(res, mul(dfs(i, m), dfs(n - i, m))); 
    }
    for (int i = 1; i <= m; i ++) {
        pls(res, mul(dfs(n, i), dfs(n, m - i)));
    }
    return res;
}

int main() {
    
    freopen("cake.in", "r", stdin);
    freopen("cake.out", "w", stdout);
    
    memset(f, -1, sizeof(f));
    f[1][1] = 1;
    
    cin >> n >> m;
    cout << dfs(n, m) << endl;
    
    return 0; 
}
最后修改:2019 年 08 月 24 日 08 : 54 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论