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