fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define SPED                                                                                                           \
  4.     ios_base::sync_with_stdio(false);                                                                                  \
  5.     cin.tie(0);                                                                                                        \
  6.     cout.tie(0);
  7.  
  8. #define endl "\n"
  9. #define fi first
  10. #define se second
  11. #define lint long long
  12. #define fami signed
  13. #define lore main
  14. #define freefire freopen
  15. #define int lint
  16.  
  17. const lint INF = 0x1f1f1f1f1f1f1f1f;
  18. const lint NEG = 0xE1E1E1E1E1E1E1E1;
  19. const lint mod = 1e9 + 19972207;
  20.  
  21. using namespace std;
  22.  
  23. int n, k, st;
  24. lint fact[900006], inv[900006];
  25. lint dp[900006], nw[900006];
  26. lint a[900006], b[900006];
  27.  
  28. lint binpow(lint x, lint k)
  29. {
  30.     if (k == 0)
  31.         return 1;
  32.  
  33.     lint temp = binpow(x, k >> 1);
  34.     temp = (temp * temp) % mod;
  35.  
  36.     if (k & 1)
  37.         temp = (temp * x) % mod;
  38.  
  39.     return temp;
  40. }
  41.  
  42. void reset()
  43. {
  44.     fill(a, a + 1 + n, 0);
  45.     fill(b, b + 1 + n, 0);
  46.     fill(dp, dp + 1 + k, 0);
  47.     fill(nw, nw + 1 + k, 0);
  48. }
  49.  
  50. fami lore()
  51. {
  52.     if (fopen("recruitment.inp", "r"))
  53.     {
  54.         freefire("recruitment.inp", "r", stdin);
  55.         freefire("recruitment.out", "w", stdout);
  56.     }
  57.  
  58.     SPED;
  59.     fact[0] = 1;
  60.  
  61.     for (int i = 1; i <= 900000; ++i)
  62.         fact[i] = (fact[i - 1] * i) % mod;
  63.  
  64.     inv[900000] = binpow(fact[900000], mod - 2);
  65.  
  66.     for (int i = 900000 - 1; i >= 0; i--)
  67.         inv[i] = (inv[i + 1] * (i + 1)) % mod;
  68.  
  69.     cin >> st;
  70.  
  71.     while (st--)
  72.     {
  73.         cin >> n >> k;
  74.  
  75.         for (int r = 0; r < k; ++r)
  76.             dp[r] = 0;
  77.  
  78.         if (k >= 1)
  79.             dp[0] = 1;
  80.  
  81.         for (int t = 2; t <= n - 1; ++t)
  82.         {
  83.             for (int r = 0; r < k; ++r)
  84.                 nw[r] = 0;
  85.  
  86.             lint S = 0;
  87.  
  88.             for (int r = 0; r < k; ++r)
  89.                 S = (S + dp[r]) % mod;
  90.  
  91.             nw[0] = S;
  92.  
  93.             for (int r = 0; r + 1 < k; ++r)
  94.                 nw[r + 1] = (nw[r + 1] + dp[r] * (t - 1)) % mod;
  95.  
  96.             b[t] = (dp[k - 1] * (t - 1)) % mod;
  97.  
  98.             for (int r = 0; r < k; ++r)
  99.                 dp[r] = nw[r] % mod;
  100.         }
  101.  
  102.         a[0] = 1;
  103.  
  104.         for (int m = 1; m <= n; ++m)
  105.         {
  106.             lint sum = 0;
  107.  
  108.             for (int t = 1; t <= m + 1; ++t)
  109.             {
  110.                 lint perm = (fact[m] * inv[m - (t - 1)]) % mod;
  111.                 sum = (sum + perm * t) % mod;
  112.             }
  113.  
  114.             a[m] = sum;
  115.         }
  116.  
  117.         lint res = 0;
  118.  
  119.         for (int i = k; i <= n - 1; ++i)
  120.         {
  121.             lint head = (((fact[n - 1] * inv[i]) % mod) * inv[n - 1 - i]) % mod;
  122.             lint tail = a[n - i - 1];
  123.             lint add = (((head * b[i]) % mod) * tail) % mod;
  124.             res = (res + add) % mod;
  125.         }
  126.  
  127.         cout << res  << endl;
  128.         reset();
  129.     }
  130. }
Success #stdin #stdout 0.02s 18640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OjzLfA
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!