Dang_Quan_10_Tin

Untitled

Feb 22nd, 2021
389
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using ld = long double;
  5. using ull = unsigned long long;
  6.  
  7. const bool typetest = 0;
  8. const int N = 3e2 + 5;
  9. const ll mod = 1e9 + 7;
  10. int n, m, l;
  11. ll dp[N][N][2];
  12. ll gt[N], rgt[N];
  13.  
  14. void Read()
  15. {
  16.     cin >> n >> m >> l;
  17. }
  18.  
  19. ll Pow(ll a, ll b)
  20. {
  21.     ll ans(1);
  22.     for (; b > 0; b >>= 1)
  23.     {
  24.         if (b & 1)
  25.             ans = ans * a % mod;
  26.         a = a * a % mod;
  27.     }
  28.     return ans;
  29. }
  30.  
  31. ll C(int k, int n)
  32. {
  33.     if (n < k)
  34.         return 0;
  35.     return gt[n] * rgt[k] % mod * rgt[n - k] % mod;
  36. }
  37.  
  38. void Solve()
  39. {
  40.     gt[0] = rgt[0] = 1;
  41.     for (int i = 1; i <= n; ++i)
  42.     {
  43.         gt[i] = gt[i - 1] * i % mod;
  44.         rgt[i] = Pow(gt[i], mod - 2);
  45.     }
  46.     dp[0][0][0] = 1;
  47.     for (int i = 0; i <= n; ++i)
  48.         for (int j = 0; j <= m; ++j)
  49.         {
  50.             //cout << i << " " << j << " " << 0 << ": " << dp[i][j][0] << "\n";
  51.             //cout << i << " " << j << " " << 1 << ": " << dp[i][j][1] << "\n";
  52.             (dp[i + 1][j][l == 1] += dp[i][j][0]) %= mod;
  53.             (dp[i + 1][j][1] += dp[i][j][1]) %= mod;
  54.             if (l >= 2 && i + 2 <= n && j + 1 <= m)
  55.             {
  56.                 (dp[i + 2][j + 2][l == 2] += dp[i][j][0] * C(1, n - i - 1) % mod) %= mod;
  57.                 (dp[i + 2][j + 1][l == 2] += dp[i][j][0] * C(1, n - i - 1) % mod) %= mod;
  58.                 (dp[i + 2][j + 2][1] += dp[i][j][1] * C(1, n - i - 1) % mod) %= mod;
  59.                 (dp[i + 2][j + 1][1] += dp[i][j][1] * C(1, n - i - 1) % mod) %= mod;
  60.             }
  61.             for (int k = 3; k <= l && k + i <= n && k + j - 1 <= m; ++i)
  62.             {
  63.                 (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;
  64.                 (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;
  65.                 (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;
  66.                 (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;
  67.             }
  68.         }
  69.     cout << dp[n][m][1];
  70. }
  71.  
  72. int32_t main()
  73. {
  74.     ios::sync_with_stdio(0);
  75.     cin.tie(0);
  76.     cout.tie(0);
  77.     int t(1);
  78.     if (typetest)
  79.         cin >> t;
  80.     for (int _ = 1; _ <= t; ++_)
  81.     {
  82.         Read();
  83.         Solve();
  84.     }
  85. }
RAW Paste Data