Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- int const N = 2009;
- int const mod = 1e9 + 7;
- typedef pair <ll, ll> ii;
- long long n, p, q, C[N][N], dp[N][N];
- long long res;
- long long Count (int x, int y) {
- return dp[x - 1][y - 1];
- }
- void Sub2() {
- dp[1][1] = 1;
- for (int i = 2; i <= n; i++)
- for (int j = 1; j <= min((ll) i, p); j++)
- dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * (i - 1)) % mod;
- cout << dp[n - 1][p - 1];
- }
- long long f[509][509], g[509][509];
- void Sub3() {
- f[1][1] = 1;
- for (int i = 2; i <= n; i++) {
- for (int pp = 0; pp <= p; pp++)
- for (int qq = 0; qq <= q; qq++)
- g[pp][qq] = f[pp][qq];
- for (int pp = 1; pp <= p; pp++)
- for (int qq = 1; qq <= q; qq++)
- f[pp][qq] = (g[pp - 1][qq] + g[pp][qq - 1] + g[pp][qq] * (i - 2)) % mod;
- }
- cout << f[p][q];
- }
- void Sub4() {
- for (int i = 0; i <= 2000; i++)
- C[0][i] = 1;
- for (int i = 1; i <= 2000; i++)
- for (int j = 1; j <= i; j++)
- C[j][i] = (C[j][i - 1] + C[j - 1][i - 1]) % mod;
- dp[1][1] = dp[0][0] = 1;
- for (int i = 2; i <= n; i++)
- for (int j = 1; j <= min((ll) i, max(p, q)); j++)
- dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * (i - 1)) % mod;
- for (int i = 1; i <= n; i++)
- res = (res + (C[i - 1][n - 1] * Count(i, p) % mod) * Count(n - i + 1, q) % mod) % mod;
- cout << res;
- }
- int main ()
- {
- cin >> n >> p >> q;
- if (q == 1) Sub2();
- else if (n <= 500) Sub3();
- else Sub4();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment