Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1937
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1937
Curious Guardians
By Stefano Tommasini 
Brazil
Timelimit: 1
Oa is one of the ancient worlds of the DC universe, it is there that inhabit the guardians of the universe. They administer the Green Lantern Corps, a major force in the universe! Everyone knows that the Green Lanterns can fly because of the power of the ring, but not all the inhabitants of Oa are part of the troop. For these people is difficult getting between cities, as there are no roads!
The guardians want to connect the cities of Oa building some roads. There are N cities in Oa, and they want to build N-1 road of both hands, so that you can get from one city to any other directly or indirectly. The guardians also do not want too much focus any city, so they established that no city can have more than K roads. For example, if we have three cities and K equals 2, we have three options:
The guardians though, are very curious, and asked the Green Lanterns if they were able to tell how many ways you can build N-1 road obeying these restrictions. Your task, as a member of the Green Lantern Corps is N and K data, satisfy the curiosity of guardians.
Input
The input consists of a single line containing two integers N (1 ≤ N ≤ 102) and K (1 ≤ K ≤ N).
Output
Your program should produce a single line containing a single integer, the problem response. As this response may be very large, print it module of 109 + 7.
| Input Samples | Output Samples |
|
3 2 |
3 |
|
4 1 |
0 |
|
4 3 |
16 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
ll dp[105][105];
ll comb[105][105];
int N;
void calc()
{
comb[0][0] = 0;
for (int i = 1; i < = 101; ++i)
{
comb[i][0] = comb[0][i] = 1;
for (int j = 1; j < = i; ++j)
{
comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % MOD;
// cout << "Comb[ " << i << " ] [ " << j << " ] = " << comb[i][j] << '\n';
}
}
}
ll solve(int n, int k)
{
if (k == 1)
if (n < = 1) return 1;
else return 0;
if (n < = 1) return 1;
ll &ans = dp[n][k];
if (ans == -1)
{
ans = 0;
for (int i = 1; i < = n; ++i)
{
ans += comb[n - 1][i - 1] * i * solve(n - i, k - 1) * solve(i - 1, k - 1);
}
}
return ans;
}
int main()
{
ios_base :: sync_with_stdio(0); cin.tie(0);
calc();
int k;
cin >> N >> k;
memset(dp, -1, sizeof dp);
cout << solve(N - 1, k) << '\n';
}
Input
Output