fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 2e3;
  9. const int MOD = 1e9 + 7;
  10.  
  11. int n, s, t;
  12. ll dp[maxn + 10][maxn + 10];
  13.  
  14. void add(ll &a, ll b)
  15. {
  16.     b %= MOD;
  17.     a += b;
  18.     if (a >= MOD)
  19.         a -= MOD;
  20. }
  21.  
  22. int main()
  23. {
  24.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  25.     if (fopen("KANGAROO.INP", "r"))
  26.     {
  27.         freopen("KANGAROO.INP", "r", stdin);
  28.         freopen("KANGAROO.OUT", "w", stdout);
  29.     }
  30.  
  31.     cin >> n >> s >> t;
  32.     dp[0][0] = 1;
  33.     for (int i = 1; i <= n; i++)
  34.         for (int j = 1; j <= n; j++)
  35.         {
  36.             if (i == s)
  37.             {
  38.                 add(dp[i][j], dp[i - 1][j - 1]);
  39.                 if (i > t && i < n)
  40.                     add(dp[i][j], (j - 1) * dp[i - 1][j]);
  41.                 else if (i > t)
  42.                     add(dp[i][j], dp[i - 1][j]);
  43.                 else
  44.                     add(dp[i][j], j * dp[i - 1][j]);
  45.             }
  46.             else if (i == t)
  47.             {
  48.                 add(dp[i][j], dp[i - 1][j - 1]);
  49.                 if (i > s && i < n)
  50.                     add(dp[i][j], (j - 1) * dp[i - 1][j]);
  51.                 else if (i > s)
  52.                     add(dp[i][j], dp[i - 1][j]);
  53.                 else
  54.                     add(dp[i][j], j * dp[i - 1][j]);
  55.             }
  56.             else
  57.             {
  58.                 add(dp[i][j], dp[i - 1][j - 1]);
  59.                 if (i > max(s, t) && i < n)
  60.                     add(dp[i][j], j * (j - 1) * dp[i - 1][j + 1]);
  61.                 else if (i > max(s, t))
  62.                     add(dp[i][j], dp[i - 1][j + 1]);
  63.                 else if (i > min(s, t))
  64.                     add(dp[i][j], j * j * dp[i - 1][j + 1]);
  65.                 else
  66.                     add(dp[i][j], j * (j + 1) * dp[i - 1][j + 1]);
  67.             }
  68.         }
  69. //    for (int i = 1; i <= n; i++)
  70. //    {
  71. //        for (int j = 1; j <= n; j++)
  72. //            cout << dp[i][j] << ' ';
  73. //        el;
  74. //    }
  75.     cout << dp[n][1];
  76. }
  77.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/A1vpmP
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!