Advertisement
Guest User

Untitled

a guest
Apr 28th, 2019
346
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.73 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. typedef pair<int,int> pii;
  6. const int inf_int = 1e9;
  7. #define fi first
  8. #define se second
  9. #define sz(x)  ((int)x.size())
  10.  
  11. #define dout if(debug) cout
  12. #define pb push_back
  13.  
  14. const int MAXN = 1e5 + 100;
  15.  
  16. bool debug = 0;
  17.  
  18. vector<int> g[MAXN];
  19.  
  20. const ll mod = 1e9+7;
  21.  
  22. ll a[MAXN];
  23.  
  24. ll bin_pow(ll a,int n){
  25.     ll res = 1;
  26.     while(n){
  27.         if(n&1)
  28.             res = (res * a)%mod;
  29.         a = (a * a)%mod;
  30.         n>>=1;
  31.     }
  32.     return res;
  33. }
  34.  
  35.  
  36. void solve(){
  37.     int n;
  38.     cin >> n;
  39.     ll X,Y;
  40.     cin >> X >> Y;
  41.     for(int i=1;i<=n;++i){
  42.         cin >> a[i];
  43.     }
  44.  
  45.  
  46.  
  47.  
  48.  
  49.     ll p = ( X * bin_pow(Y,mod-2) )%mod;
  50.     ll np = (mod + 1 - p);
  51.  
  52.  
  53.  
  54.     ll my_dp[2][2];
  55.  
  56.  
  57.     dout <<"P NP : " << p <<" "<<np<<endl;
  58.     ll ans = 0;
  59.     for(int bit=0;bit<=29;++bit){
  60.         my_dp[0][1] = 0;
  61.         my_dp[0][0] = 1;
  62.  
  63.         dout <<"bit " <<bit<<endl;
  64.  
  65.         for(int i=1;i<=n;++i){
  66.  
  67.             int cur_x = 0;
  68.             if(a[i]&(1<<bit))
  69.                 cur_x = 1;
  70.  
  71.  
  72.             int cur = (i&1);
  73.             dout <<"!! "<<my_dp[cur^1][0 ^ cur_x] * p<<" "<<my_dp[cur^1][0] * np<<endl;
  74.  
  75.             my_dp[cur][1] =  ( my_dp[cur ^ 1][1 ^ cur_x] * p + my_dp[cur ^ 1][1] * np )%mod;
  76.             my_dp[cur][0] = (my_dp[cur^1][0 ^ cur_x] * p + my_dp[cur^1][0] * np )%mod;
  77.  
  78.             dout <<i <<" : "<<my_dp[cur][0] <<" "<<my_dp[cur][1] <<" "<<cur_x<<endl;
  79.  
  80.  
  81.         }
  82.         ll x = (1<<bit);
  83.         x = (x * x)%mod;
  84.         ans += my_dp[n&1][1] * x;
  85.         ans %= mod;
  86.     }
  87.     dout << ans<<endl;
  88.  
  89.     ll dp[2][2][2];
  90.     for(int bit0 = 0;bit0 <= 29;++bit0){
  91.         for(int bit1 = bit0+1;bit1 <= 29;++bit1){
  92.             memset(dp,0,sizeof dp);
  93.             dp[0][0][0] = 1;
  94.             for(int i=1;i<=n;++i){
  95.                 int cur = (i&1);
  96.                 int cur_0 = 0;
  97.                 int cur_1 = 0;
  98.                 if(a[i]&(1<<bit0))
  99.                     cur_0 = 1;
  100.                 if(a[i]&(1<<bit1))
  101.                     cur_1 = 1;
  102.  
  103.                 for(int i=0;i<2;++i){
  104.                     for(int j=0;j<2;++j){
  105.                         dp[cur][i][j] = (dp[cur ^ 1][i^cur_0][j^cur_1] * p + dp[cur^1][i][j] * np)%mod;
  106.                     }
  107.                 }
  108.  
  109.             }
  110.  
  111.             ll val = (1ll<<bit0) * (1ll<<bit1);
  112.             val = val%mod;
  113.             val = (val * 2)%mod;
  114.  
  115.             ans+= (val * dp[n&1][1][1] )%mod;
  116.         }
  117.     }
  118.     ans%=mod;
  119.  
  120.     cout << ans<<"\n";
  121.  
  122.  
  123.  
  124. }
  125.  
  126. int main(){
  127.    #ifdef zxc
  128.         debug = 1;
  129.         freopen("input.txt","r",stdin);
  130.    #endif
  131.  
  132.    ios_base::sync_with_stdio(0);
  133.    cin.tie(0);
  134.    cout.tie(0);
  135.  
  136.    int t = 1;
  137.    while(t--)
  138.     solve();
  139.  
  140. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement