# Untitled

a guest
Apr 28th, 2019
346
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }