fork download
copy 
  1. //      - Art -
  2. #pragma GCC optimize("O3,unroll-loops") // O2
  3. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  4. #include <bits/stdc++.h>
  5.  
  6. #define el              cout << '\n'
  7.  
  8. #define FOR(i, a, b)    for (int i = (a), _b = (b); i <= _b; ++i)
  9. #define REV(i, b, a)    for (int i = (b), _a = (a); i >= _a; --i)
  10. #define REP(i, c)       for (int i = 0, _c = (c); i < _c; ++i)
  11.  
  12. const int N = 1e5 + 7;
  13. const int MOD = 1e9 + 7;
  14.  
  15. void add(int &a, int b) {a += b; if (a >= MOD) a -= MOD;}
  16. void sub(int &a, int b) {a -= b; if (a < 0) a += MOD;}
  17. #define multi(a, b)     (1ll * (a) * (b) % MOD)
  18. #define div(a, b)       (1ll * (a) * inverse(b) % MOD)
  19.  
  20. using namespace std;
  21.  
  22. int f[N];
  23.  
  24. int main() {
  25.  
  26.     #define name "art"
  27.     if (fopen(name".inp", "r")) {
  28.         freopen(name".inp", "r", stdin);
  29.         freopen(name".out", "w", stdout);
  30.     }
  31.  
  32.     ios_base::sync_with_stdio(false);
  33.     cin.tie(0); cout.tie(0);
  34.  
  35.     auto binpow = [&](int a, int b) -> int {
  36.         int res = 1;
  37.         while (b > 0) {
  38.             if (b & 1) {
  39.                 res = multi(res, a);
  40.             }
  41.             a = multi(a, a);
  42.             b >>= 1;
  43.         }
  44.         return res;
  45.     };
  46.     auto num_trees = [&](int n) -> int {
  47.         return binpow(n, n - 2);
  48.     };
  49.  
  50.     int n, k;
  51.     cin >> n >> k;
  52.     // => sz * (n-sz) <= k
  53.  
  54.     // case: 1 * (n-1) <= k (k >= n-1 -> ok)
  55.     if (k == n - 1) {
  56.         cout << n, el;
  57.         return 0;
  58.     }
  59.  
  60.     // best case: n/2 * (n-n/2) <= k -> n*n <= 4k
  61.     if (n * n - 4 * k <= 0) {
  62.         cout << num_trees(n), el;
  63.         return 0;
  64.     }
  65.  
  66.     f[0] = f[1] = 1;
  67.     FOR (nodes, 2, n) {
  68.         f[nodes] = num_trees(nodes);
  69. //        cout << f[nodes], el;
  70.         if (nodes * nodes - 4 * k <= 0) {
  71.             continue;
  72.         }
  73. //        cout << nodes << ' ';
  74.         FOR (sz, 1, nodes) {
  75.             if (sz * (nodes - sz) <= k) {
  76.                 continue;
  77.             }
  78.             sub(f[nodes], multi(multi(f[sz], f[nodes - sz]), sz * (nodes - sz)));
  79.         }
  80.         // el;
  81.     }
  82.     cout << f[n], el;
  83.  
  84.     return 0;
  85. }
  86.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
4 4
stdout
copy 
16
https://ideone.com/Sb6xka
language:
C++14 (gcc 8.3)
created:
1 day 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!