Guest User

Untitled

a guest
May 25th, 2020
64
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define endl '\n'
  5. #define sz(v) (int)v.size()
  6. #define all(v) v.begin(), v.end()
  7. void dbg_out() { cerr << "\b\b]\n"; }
  8. template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ cerr << H << ", "; dbg_out(T...);}
  9. #define watch(...) cerr << "[" << #__VA_ARGS__ << "]: [", dbg_out(__VA_ARGS__)
  10.  
  11.  
  12. /****************************** CODE IS HERE ***********************************/
  13.  
  14. const int mod = 998244353;
  15. const int lg = 21, N = 1e6 + 2;
  16.  
  17. int power(ll a, ll b){
  18.   ll res = 1;
  19.   while(b){
  20.     if(b & 1)
  21.       res = (res * a) % mod;
  22.     a = (a * a) % mod;
  23.     b >>= 1;
  24.   }
  25.   return res;
  26. }
  27.  
  28.  
  29. int main(){
  30.     ios_base::sync_with_stdio(false); cin.tie(nullptr);
  31.  
  32.     int n, q; cin >> n >> q;
  33.     vector <int> A(N+2, 0);
  34.     for (int i = 0, x; i < n; ++i){
  35.       cin >> x;
  36.       A[x]++;
  37.     }
  38.  
  39.     vector <int> res(N+2, 0);
  40.     vector <vector<int>> dp(N, vector<int> (lg, 0));
  41.  
  42.     for (int mask = 0; mask < N; ++mask){
  43.       for (int i = 0; i < lg; ++i){
  44.         if(mask & (1 << i)){
  45.           if(i == 0)
  46.             dp[mask][i] = A[mask] + A[mask^(1<<i)];
  47.           else
  48.             dp[mask][i] = dp[mask][i-1] + dp[mask^(1<<i)][i-1];
  49.         }
  50.         else{
  51.           if(i == 0)
  52.             dp[mask][i] = A[mask];
  53.           else
  54.             dp[mask][i] = dp[mask][i-1];
  55.         }
  56.       }
  57.       res[mask] = dp[mask][lg-1];
  58.     }
  59.  
  60.     while(q--){
  61.       int x; cin >> x;
  62.       ll ans = 1LL*res[x]*power(n, mod-2) % mod;
  63.       cout << ans << endl;
  64.     }
  65.  
  66.  
  67.  
  68.   return 0;
  69. }
RAW Paste Data