fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef long double ld;
  7. typedef pair<int, int> pii;
  8. typedef pair<ll, ll> pll;
  9. typedef vector<int> vi;
  10.  
  11. #define fi first
  12. #define se second
  13. #define pp push_back
  14. #define all(x) (x).begin(), (x).end()
  15. #define Ones(n) __builtin_popcount(n)
  16. #define endl '\n'
  17. #define mem(arrr, xx) memset(arrr,xx,sizeof arrr)
  18. //#define int long long
  19. #define debug(x) cout << (#x) << " = " << x << endl
  20.  
  21. void Gamal() {
  22.     ios_base::sync_with_stdio(false);
  23.     cin.tie(nullptr);
  24.     cout.tie(nullptr);
  25. #ifdef Clion
  26.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  27. #endif
  28. }
  29.  
  30. int dx[] = {+0, +0, -1, +1, +1, +1, -1, -1};
  31. int dy[] = {-1, +1, +0, +0, +1, -1, +1, -1};
  32.  
  33. const double EPS = 1e-9;
  34. const ll OO = 0X3F3F3F3F3F3F3F3F;
  35. const int N = 2030 + 5, INF = INT_MAX, MOD = 1e9 + 7, LOG = 20;
  36.  
  37. int dp[N][N], n, m, r;
  38.  
  39. int slv(int i, int leaf, int intern) {
  40.     if (i == -1) {
  41.         return 1;
  42.     }
  43.     int &ret = dp[i][leaf];
  44.     if (~ret)
  45.         return ret;
  46.     ret = 0;
  47.     // with left
  48.     if (leaf) {
  49.         ret += 1ll * leaf * slv(i - 1, leaf - (r == i), intern + 1) % m;
  50.         ret %= m;
  51.     }
  52.     // with internal
  53.     if (intern) {
  54.         ret += 1ll * intern * slv(i - 1, leaf + 1 - (r == i), intern - 1) % m;
  55.         ret %= m;
  56.     }
  57.     return ret;
  58. }
  59.  
  60. void solve() {
  61.     cin >> r >> n >> m;
  62.     r--;
  63.     mem(dp, -1);
  64.     cout << slv(n - 1, 0, 1) << endl;
  65. }
  66.  
  67.  
  68. signed main() {
  69.     Gamal();
  70.     int t = 1;
  71. //    cin >> t;
  72.     while (t--) {
  73.         solve();
  74.     }
  75. }
Success #stdin #stdout 0.01s 19616KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/JtYLsV
language:
C++14 (gcc 8.3)
created:
9 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!