Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ld = long double;
- using ull = unsigned long long;
- const bool typetest = 0;
- const int N = 3e2 + 5;
- const ll mod = 1e9 + 7;
- int n, m, l;
- ll dp[N][N][2];
- ll gt[N], rgt[N];
- void Read()
- {
- cin >> n >> m >> l;
- }
- ll Pow(ll a, ll b)
- {
- ll ans(1);
- for (; b > 0; b >>= 1)
- {
- if (b & 1)
- ans = ans * a % mod;
- a = a * a % mod;
- }
- return ans;
- }
- ll C(int k, int n)
- {
- if (n < k)
- return 0;
- return gt[n] * rgt[k] % mod * rgt[n - k] % mod;
- }
- void Solve()
- {
- gt[0] = rgt[0] = 1;
- for (int i = 1; i <= n; ++i)
- {
- gt[i] = gt[i - 1] * i % mod;
- rgt[i] = Pow(gt[i], mod - 2);
- }
- dp[0][0][0] = 1;
- for (int i = 0; i <= n; ++i)
- for (int j = 0; j <= m; ++j)
- {
- //cout << i << " " << j << " " << 0 << ": " << dp[i][j][0] << "\n";
- //cout << i << " " << j << " " << 1 << ": " << dp[i][j][1] << "\n";
- (dp[i + 1][j][l == 1] += dp[i][j][0]) %= mod;
- (dp[i + 1][j][1] += dp[i][j][1]) %= mod;
- if (l >= 2 && i + 2 <= n && j + 1 <= m)
- {
- (dp[i + 2][j + 2][l == 2] += dp[i][j][0] * C(1, n - i - 1) % mod) %= mod;
- (dp[i + 2][j + 1][l == 2] += dp[i][j][0] * C(1, n - i - 1) % mod) %= mod;
- (dp[i + 2][j + 2][1] += dp[i][j][1] * C(1, n - i - 1) % mod) %= mod;
- (dp[i + 2][j + 1][1] += dp[i][j][1] * C(1, n - i - 1) % mod) %= mod;
- }
- for (int k = 3; k <= l && k + i <= n && k + j - 1 <= m; ++i)
- {
- (dp[i + k][j + k][k == l] += dp[i][j][0] * C(k - 1, n - i - 1) % mod * gt[k - 1] % mod * rgt[2] % mod) %= mod;
- (dp[i + k][j + k - 1][k == l] += dp[i][j][0] * C(k - 1, n - i - 1) % mod * gt[k] % mod * rgt[2] % mod) %= mod;
- (dp[i + k][j + k][1] += dp[i][j][1] * C(k - 1, n - i - 1) % mod * gt[k - 1] % mod * rgt[2] % mod) %= mod;
- (dp[i + k][j + k - 1][1] += dp[i][j][1] * C(k - 1, n - i - 1) % mod * gt[k] % mod * rgt[2] % mod) %= mod;
- }
- }
- cout << dp[n][m][1];
- }
- int32_t main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int t(1);
- if (typetest)
- cin >> t;
- for (int _ = 1; _ <= t; ++_)
- {
- Read();
- Solve();
- }
- }
RAW Paste Data