问题描述

小蓝和小桥是两位年轻的建筑师，他们正在设计一座新的城市。

在这个城市中，有 N 条街道，每条街道上都有 M 个位置可以建造房屋（一个位置只能建造一个房屋）。建造一个房屋的费用为 1 元，小蓝和小桥共有 K 元的建造预算。

现在，他们想知道，一共有多少种建造方案，满足以下要求：

• 在每条街道上，至少建一个房屋。
• 建造的总成本不能超过 K 元。

由于方案数可能很大，他们只需要输出答案对 109+7 取模的结果。

输入格式

一行三个整数 N,M（1≤N,M≤50） 和 K（1≤K≤N⋅M），分别表示街道数、街道的位置数和预算。

输出格式

一个整数，表示满足条件的建造方案数对 109+7 取模的结果。

样例输入

2 3 5

样例输出

8

题解

dp[i][j] 表示到第i条街道共修了j个房屋的方案数

假设当前街道要建l个房子，那么

dp[i][j] += dp[i - 1][j - l], l <= m && j - l >= i - 1

(当前街道不能建超过m个房屋，并且对于前i - 1个街道，修建的房屋至少是i - 1)。

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 55;
ll p = 1e9 + 7;
ll dp[N][N * N];int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int n,m, k;cin >> n >> m >> k;for(int i = 0;i <= k;i ++)dp[0][i] = 1;for(int i = 1;i <= n;i ++)for(int j = 1;j <= k;j ++)for(int l = 1;l <= m && j - l >= i - 1;l ++)dp[i][j] = (dp[i][j] + dp[i - 1][j - l]) % p;cout << dp[n][k] << '\n';return 0;
}