fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define all(c) ((c).begin()), ((c).end())
  6. #define sz(x) ((int)(x).size())
  7.  
  8. #ifdef LOCAL
  9. #include <print.h>
  10. #else
  11. #define trace(...)
  12. #define endl "\n" // remove in interactive
  13. #endif
  14.  
  15. const int N = 33;
  16.  
  17. int power(int x, int a, int p){
  18.     int ret = 1;
  19.     for(; a; a >>= 1, x = (x * (ll) x) % p) if(a & 1) ret = (ret * (ll) x) % p;
  20.     return ret;
  21. }
  22. pair<ll, int> dp[2][1400000];
  23. int main(){
  24.     ios_base::sync_with_stdio(false); 
  25.     cin.tie(NULL); // Remove in interactive problems
  26.     int n, p;
  27.     cin >> n;
  28.     cin >> p;
  29.  
  30.     vector<int> fact(N * N, 0), invfact(N * N, 0);
  31.     fact[0] = 1;
  32.     for(int i = 1; i < N * N; i++){
  33.         fact[i] = i * (ll) fact[i - 1] % p;
  34.     }
  35.     invfact[N*N - 1] = power(fact[N*N - 1], p - 2, p);
  36.     for(int i = N*N - 2; i >= 0; i--){
  37.         invfact[i] = (i + 1) * (ll) invfact[i + 1] % p;
  38.     }
  39.     assert(invfact[0] == 1);
  40.     vector<int> s(n), t(n);
  41.     ll MASK = 0;
  42.     int delta = 0;
  43.     for(int i = 0; i < n; i++){
  44.         cin >> s[i]; 
  45.         s[i]--;
  46.         delta-=s[i];
  47.     }
  48.     for(int i = 0; i < n; i++){
  49.         cin >> t[i]; 
  50.         t[i]--;
  51.         delta += t[i];
  52.     }
  53.     if(delta<0){
  54.         cout << 0 << endl;
  55.         return 0;
  56.     }
  57.     dp[0][0] = {(1LL << n) - 1, fact[delta]};
  58.     sort(all(s));
  59.     sort(all(t));
  60.     int I[2];
  61.     I[0] = 1;
  62.     function<void(ll, int, int, int)> appendMasks = [&](ll mask, int i, int d, int id){
  63.         if(d > i + 1) return;
  64.         if(d == 0){
  65.             dp[id][I[id]++] = {(1LL << n) - 1 - mask, 0};
  66.             return;
  67.         }
  68.         if(s[i] <= t[d - 1]) appendMasks(mask | (1LL << i), i - 1, d - 1, id);
  69.         appendMasks(mask, i - 1, d, id);
  70.     };
  71.  
  72.     for(int pos = 0, id = 0; pos < n; pos++, id ^= 1){
  73.         int x = t[pos];
  74.         I[id ^ 1] = 0;
  75.         int maxi = 0;
  76.         while(maxi < n && s[maxi] <= x) maxi++; maxi--;
  77.         appendMasks(0LL, maxi, pos + 1, id ^ 1);
  78.         for(int u = 0; u <= maxi; u++){
  79.             int ptr = 0;
  80.             for(int i = 0; i < I[id]; i++){
  81.                 ll mask = dp[id][i].first;
  82.                 int value = dp[id][i].second;
  83.                 ll newmask = mask & (~(1LL << u));
  84.                 if(newmask == mask) continue;
  85.                 while(ptr < I[id ^ 1] && dp[id ^ 1][ptr].first < newmask) ptr++;
  86.                 if(dp[id ^ 1][ptr].first == newmask) dp[id ^ 1][ptr].second = (dp[id ^ 1][ptr].second + value * (ll) invfact[x - s[u]]) % p;
  87.             }
  88.         }
  89.     }
  90.     cout << dp[n & 1][0].second << endl;
  91. }
Runtime error #stdin #stdout #stderr 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
prog: prog.cpp:39: int main(): Assertion `invfact[0] == 1' failed.
https://ideone.com/mehjqv
language:
C++14 (gcc 8.3)
created:
36 days ago
visibility:
secret

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!