fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. //#define int long long
  3. #define FOR(i,a,b) for(int i = (a); i <= (b); i++)
  4. #define RE(i,n) FOR(i,1,n)
  5. #define REP(i,n) FOR(i,0,(n)-1)
  6. #define MP make_pair
  7. #define PB push_back
  8. #define st first
  9. #define nd second
  10. #define SZ(x) ((int)(x).size())
  11. #ifndef LOCAL
  12. #define cerr if(0)cout
  13. #endif
  14. using namespace std;
  15. const int N = 2e2 + 5;
  16.  
  17. int dp[N][N][N];
  18. int newt[N][N];
  19. int inv[N];
  20. int spow(int a, int b, int P) {
  21.   int r = 1;
  22.   while (b) {
  23.     if (b % 2) {
  24.       r = 1ll * r * a % P;
  25.     }
  26.     a = 1ll * a * a % P;
  27.     b /= 2;
  28.   }
  29.   return r;
  30. }
  31. int Inv(int a, int P) {
  32.   return spow(a, P - 2, P);
  33. }
  34. int P;
  35. #undef int
  36. int main() {
  37. #define int long long
  38.   ios_base::sync_with_stdio(0);
  39.   cin.tie(0);
  40.  
  41.   int n, max_d;
  42.   cin>>n>>max_d>>P;
  43.   if (n == 1) {
  44.     cout<<(max_d == 0)<<endl;
  45.     return 0;
  46.   }
  47.   if (n == 2) {
  48.     cout<<(max_d == 1)<<endl;
  49.     return 0;
  50.   }
  51.   if (max_d <= 1) {
  52.     cout<<"0\n";
  53.     return 0;
  54.   }
  55.   int npar = max_d % 2;
  56.   max_d /= 2;
  57.   RE (i, n) {
  58.     inv[i] = Inv(i, P);
  59.   }
  60.   dp[1][0][0] = 1;
  61.   RE (dep, max_d) {
  62.     dp[1][dep][0] = 1;
  63.     FOR (sz, 2, n) {
  64.       RE (max_son, sz - 1) {
  65.         // Wkladamy synow wielkosci max_son
  66.         // aby sumarycznie miec sz wierzcholkow
  67.         // Albo nie dokladamy nikogo (dp[max_son][dep - 1][max_son - 1])
  68.         // albo dokladamy l synow wielkosci max_son
  69.         // i wtedy bierzemy wynik z dp[prev][dep][prev - 1]
  70.         // l synow takiej wielkosci wybieramy ilestam sposobow
  71.         int cur = dp[max_son][dep - 1][max_son - 1];
  72.         dp[sz][dep][max_son] = dp[sz][dep][max_son - 1];
  73.         for (int l = 1; l * max_son < sz; l++) {
  74.           int prev = sz - l * max_son;
  75.           dp[sz][dep][max_son] = (dp[sz][dep][max_son] + 1ll * dp[prev][dep][min(prev, max_son) - 1] * cur) % P;
  76.           cur = 1ll * cur * inv[l + 1] % P * (dp[max_son][dep - 1][max_son - 1] + l) % P;
  77.           //cerr<<cur<<endl;
  78.         }
  79.         cerr<<"dp["<<sz<<"]["<<dep<<"]["<<max_son<<"]="<<dp[sz][dep][max_son]<<endl;
  80.       }
  81.     }
  82.   }
  83.   long long res = 0;
  84.   if (npar) {
  85.     for (int l = 1; 2 * l < n; l++) {
  86.       int r = n - l;
  87.       res += 1ll * (dp[l][max_d][l - 1] - dp[l][max_d - 1][l - 1] + P) * (dp[r][max_d][r - 1] - dp[r][max_d - 1][r - 1] + P);
  88.       res %= P;
  89.     }
  90.     if (n % 2 == 0) {
  91.       long long K = dp[n / 2][max_d][n / 2 - 1] - dp[n / 2][max_d - 1][n / 2 - 1] + P;
  92.       res += 1ll * K * (K + 1) / 2;
  93.     }
  94.     cout<<res % P<<endl;
  95.   } else {
  96.     res = (dp[n][max_d][n - 1] - dp[n][max_d - 1][n - 1] + P) % P;
  97.     RE (big_son, n - 1) {
  98.       long long BIG_DEEP = dp[big_son][max_d - 1][big_son - 1];
  99.       if (max_d >= 2) {
  100.         BIG_DEEP = (BIG_DEEP - dp[big_son][max_d - 2][big_son - 1] + P) % P;
  101.       }
  102.       res = (res - (BIG_DEEP * dp[n - big_son][max_d - 1][n - big_son - 1]) % P + P) % P;
  103.     }
  104.     cout<<res<<endl;
  105.   }
  106.  
  107.   return 0;
  108. }
Success #stdin #stdout 0s 37280KB
comments (?)
stdin
copy 
6 3 13
stdout
copy 
2
https://ideone.com/ENhisf
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!