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.  
  16. const lint INF = 0x1f1f1f1f1f1f1f1f;
  17. const lint NEG = 0xE1E1E1E1E1E1E1E1;
  18. const lint mod = 1e9 + 19972207;
  19.  
  20. using namespace std;
  21.  
  22. int t;
  23. lint ways;
  24. lint p[260005], gt[260005], inv[260005], a[260005];
  25. int n;
  26. lint k;
  27. vector<lint> maku;
  28.  
  29. lint binpow(lint x, lint SA)
  30. {
  31.     if (SA == 0)
  32.         return 1;
  33.     lint temp = binpow(x, SA >> 1);
  34.     temp *= temp;
  35.     temp %= mod;
  36.     if (SA & 1)
  37.     {
  38.         temp *= x;
  39.         temp %= mod;
  40.     }
  41.     return temp;
  42. }
  43.  
  44. void Try(int idx, int cnt, int mask)
  45. {
  46.     if (idx == n)
  47.     {
  48.         if (cnt == 0)
  49.             maku.emplace_back(mask);
  50.         return;
  51.     }
  52.     if (cnt < 0)
  53.         return;
  54.  
  55.     Try(idx + 1, cnt + 1, mask | (1 << idx)); /// mask 1 là bit đó cho sang trái, else cho sang phải
  56.     Try(idx + 1, cnt - 1, mask);
  57. }
  58.  
  59. string debug(lint masku)
  60. {
  61.     string res;
  62.     for (int i = 0; i < n; i++)
  63.         res += char('0' + (masku >> i & 1));
  64.     // reverse(res.begin(), res.end());
  65.     return res;
  66. }
  67.  
  68. void solve12()
  69. {
  70.     maku.clear();
  71.     Try(0, 0, 0);
  72.  
  73.     if (maku.size() < k)
  74.     {
  75.         cout << -1 << endl;
  76.         return;
  77.     }
  78.  
  79.     sort(maku.begin(), maku.end());
  80.     int cntl = 0, cntr = 0;
  81.     static int l[25], r[25];
  82.     for (int i = 0; i < n; i++)
  83.     {
  84.         if (maku[k - 1] >> i & 1)
  85.             l[++cntl] = a[i + 1];
  86.         else
  87.             r[++cntr] = a[i + 1];
  88.     }
  89.  
  90.     sort(l + 1, l + 1 + cntl, greater<int>());
  91.     sort(r + 1, r + 1 + cntr, greater<int>());
  92.  
  93.     lint res = 0;
  94.     int cnt = 1;
  95.     for (int i = 1; i <= cntl; i++)
  96.     {
  97.         res += (l[i] * p[cnt++]) % mod;
  98.         res %= mod;
  99.     }
  100.     for (int i = 1; i <= cntr; i++)
  101.     {
  102.         res += (r[i] * p[cnt++]) % mod;
  103.         res %= mod;
  104.     }
  105.  
  106.     cout << res << endl;
  107. }
  108.  
  109. void solve3()
  110. {
  111.     int cnt = 1;
  112.     lint res = 0;
  113.     for (lint i = n; i >= 1; i--)
  114.     {
  115.         res += (i * p[cnt++]) % mod;
  116.         res %= mod;
  117.     }
  118.     for (lint i = 2 * n; i >= n + 1; i--)
  119.     {
  120.         res += (i * p[cnt++]) % mod;
  121.         res %= mod;
  122.     }
  123.     cout << res << endl;
  124. }
  125.  
  126. fami lore()
  127. {
  128.     if (fopen("permutations.inp", "r"))
  129.     {
  130.         freefire("permutations.inp", "r", stdin);
  131.         freefire("permutations.out", "w", stdout);
  132.     }
  133.     SPED;
  134.     p[0] = 1;
  135.     for (int i = 1; i <= 260000; i++)
  136.     {
  137.         p[i] = p[i - 1] * 22071997;
  138.         p[i] %= mod;
  139.     }
  140.     gt[0] = 1;
  141.     for (int i = 1; i <= 260000; i++)
  142.     {
  143.         gt[i] = gt[i - 1] * i;
  144.         gt[i] %= mod;
  145.     }
  146.     inv[260000] = binpow(gt[260000], mod - 2);
  147.     for (int i = 259999; i >= 0; i--)
  148.     {
  149.         inv[i] = inv[i + 1] * (i + 1);
  150.         inv[i] %= mod;
  151.     }
  152.     iota(a + 1, a + 1 + 260000, 1);
  153.  
  154.     cin >> t;
  155.     while (t--)
  156.     {
  157.         cin >> n >> k;
  158.         if (k == 1)
  159.         {
  160.             solve3();
  161.         }
  162.         else if (n <= 13)
  163.         {
  164.             n *= 2;
  165.             solve12();
  166.         }
  167.         else
  168.             cout << -1 << endl;
  169.     }
  170. }
  171. // Let your soul wander where dreams are born.
Success #stdin #stdout 0.01s 11640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/R0DMXC
language:
C++14 (gcc 8.3)
created:
4 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!