DuongNhi99

LINEUP

Mar 10th, 2022
765
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. int const N = 2009;
  6. int const mod = 1e9 + 7;
  7. typedef pair <ll, ll> ii;
  8.  
  9. long long n, p, q, C[N][N], dp[N][N];
  10. long long res;
  11.  
  12. long long Count (int x, int y) {
  13.     return dp[x - 1][y - 1];
  14. }
  15.  
  16. void Sub2() {
  17.     dp[1][1] = 1;
  18.     for (int i = 2; i <= n; i++)
  19.         for (int j = 1; j <= min((ll) i, p); j++)
  20.             dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * (i - 1)) % mod;
  21.    
  22.     cout << dp[n - 1][p - 1];
  23. }
  24.  
  25. long long f[509][509], g[509][509];
  26.  
  27. void Sub3() {
  28.     f[1][1] = 1;
  29.    
  30.     for (int i = 2; i <= n; i++) {
  31.         for (int pp = 0; pp <= p; pp++)
  32.            for (int qq = 0; qq <= q; qq++)
  33.                 g[pp][qq] = f[pp][qq];
  34.                
  35.         for (int pp = 1; pp <= p; pp++)
  36.            for (int qq = 1; qq <= q; qq++)
  37.                 f[pp][qq] = (g[pp - 1][qq] + g[pp][qq - 1] + g[pp][qq] * (i - 2)) % mod;
  38.     }
  39.    
  40.     cout << f[p][q];
  41. }
  42.  
  43.  
  44. void Sub4() {
  45.     for (int i = 0; i <= 2000; i++)
  46.         C[0][i] = 1;
  47.     for (int i = 1; i <= 2000; i++)
  48.         for (int j = 1; j <= i; j++)
  49.             C[j][i] = (C[j][i - 1] + C[j - 1][i - 1]) % mod;
  50.            
  51.     dp[1][1] = dp[0][0] = 1;
  52.     for (int i = 2; i <= n; i++)
  53.         for (int j = 1; j <= min((ll) i, max(p, q)); j++)
  54.             dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j] * (i - 1)) % mod;
  55.            
  56.     for (int i = 1; i <= n; i++)
  57.         res = (res + (C[i - 1][n - 1] * Count(i, p) % mod) * Count(n - i + 1, q) % mod) % mod;
  58.    
  59.     cout << res;
  60. }
  61.  
  62. int main ()
  63. {
  64.     cin >> n >> p >> q;
  65.    
  66.     if (q == 1) Sub2();
  67.     else if (n <= 500) Sub3();
  68.     else Sub4();
  69.  
  70.     return 0;
  71. }
  72.  
Advertisement
Add Comment
Please, Sign In to add comment