fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "permutations"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. #define pb emplace_back
  12. #define fi first
  13. #define se second
  14. #define sz(s) (int)s.size()
  15. #define all(s) (s).begin(), (s).end()
  16. #define ms(a,x) memset(a, x, sizeof (a))
  17. #define cn continue
  18. #define re exit(0)
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef __int128 i128;
  23.  
  24. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  25. inline void rf(){
  26.     ios_base::sync_with_stdio(false);
  27.     cin.tie(nullptr); cout.tie(nullptr);
  28.     if(fopen(file".inp","r")){
  29.         freopen(file".inp","r",stdin);
  30.         freopen(file".out","w",stdout);
  31.     }
  32. }
  33.  
  34. static inline ull comb_capped(ull n, ull k, ull cap){
  35.     if(k>n) return 0;
  36.     k=min(k, n-k);
  37.     if(k==0) return 1;
  38.     i128 prod=1;
  39.     for(ull i=1;i<=k;i++){
  40.         ull num = n - (k - i);
  41.         ull den = i;
  42.         ull g = __gcd(num, den);
  43.         num/=g; den/=g;
  44.         if(den>1){
  45.             ull g2 = __gcd((ull)((ull)(prod%den)), den);
  46.             prod/=g2; den/=g2;
  47.         }
  48.         prod*= (i128)num;
  49.         if(prod > (i128)cap) return cap+1;
  50.     }
  51.     return (ull)prod;
  52. }
  53.  
  54. static inline ull pref_count(ull m, ull V, ull cap){
  55.     if(V<m) return 0;
  56.     if(V>2*m) V=2*m;
  57.     ull num = 2*m - V + 1;
  58.     ull den = m + 1;
  59.     i128 thr = (i128)cap * den;
  60.     ull limit = (ull)(thr / num) + 1;
  61.     ull c = comb_capped(V, m, limit);
  62.     if(c>limit) return cap+1;
  63.     i128 val = (i128)c * num / den;
  64.     if(val>(i128)cap) return cap+1;
  65.     return (ull)val;
  66. }
  67.  
  68. int main(){
  69.     rf();
  70.     const ll BASE = 22071997LL;
  71.     const ll MODH = 1000000000LL + 19972207LL;
  72.  
  73.     int T; 
  74.     if(!(cin>>T)) return 0;
  75.     while(T--){
  76.         ull n; unsigned long long k;
  77.         cin>>n>>k;
  78.  
  79.         ull cat_all = pref_count(n, 2*n-1, k);
  80.         if(cat_all<k){
  81.             cout<<-1<<nl;
  82.             cn;
  83.         }
  84.  
  85.         vector<int> open_pos; open_pos.reserve(n);
  86.         ull upper = 2*n-1;
  87.         for(ull m=n; m>=1; --m){
  88.             ull lo=m, hi=min(upper, 2*m-1);
  89.             while(lo<hi){
  90.                 ull mid = (lo+hi)>>1;
  91.                 ull s = pref_count(m, mid, k);
  92.                 if(s>=k) hi=mid;
  93.                 else lo=mid+1;
  94.             }
  95.             ull v=lo;
  96.             ull before = pref_count(m, v-1, k);
  97.             k -= before;
  98.             open_pos.pb((int)v);
  99.             upper = v-1;
  100.         }
  101.         sort(all(open_pos));
  102.  
  103.         vector<int> perm; perm.reserve(2*n);
  104.         for(int i=(int)open_pos.size()-1;i>=0;--i) perm.pb(open_pos[i]);
  105.         vector<char> isA(2*n+1,0);
  106.         for(int x:open_pos) isA[x]=1;
  107.         for(ull x=1;x<=2*n;++x) if(!isA[x]) perm.pb((int)x);
  108.  
  109.         ll ans=0, pw=1;
  110.         for(size_t i=1;i<=perm.size();++i){
  111.             pw = (ll)((__int128)pw * BASE % MODH);
  112.             ans = (ans + (ll)((__int128)perm[i-1]*pw % MODH)) % MODH;
  113.         }
  114.         cout<<ans<<nl;
  115.     }
  116.     return 0;
  117. }
  118.  
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
3
3 1
3 2
3 3
stdout
copy 
651078562
550406687
74112586
https://ideone.com/qIsHpu
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!