Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef pair<int,int> pii;
- const int inf_int = 1e9;
- #define fi first
- #define se second
- #define sz(x) ((int)x.size())
- #define dout if(debug) cout
- #define pb push_back
- const int MAXN = 1e5 + 100;
- bool debug = 0;
- vector<int> g[MAXN];
- const ll mod = 1e9+7;
- ll a[MAXN];
- ll bin_pow(ll a,int n){
- ll res = 1;
- while(n){
- if(n&1)
- res = (res * a)%mod;
- a = (a * a)%mod;
- n>>=1;
- }
- return res;
- }
- void solve(){
- int n;
- cin >> n;
- ll X,Y;
- cin >> X >> Y;
- for(int i=1;i<=n;++i){
- cin >> a[i];
- }
- ll p = ( X * bin_pow(Y,mod-2) )%mod;
- ll np = (mod + 1 - p);
- ll my_dp[2][2];
- dout <<"P NP : " << p <<" "<<np<<endl;
- ll ans = 0;
- for(int bit=0;bit<=29;++bit){
- my_dp[0][1] = 0;
- my_dp[0][0] = 1;
- dout <<"bit " <<bit<<endl;
- for(int i=1;i<=n;++i){
- int cur_x = 0;
- if(a[i]&(1<<bit))
- cur_x = 1;
- int cur = (i&1);
- dout <<"!! "<<my_dp[cur^1][0 ^ cur_x] * p<<" "<<my_dp[cur^1][0] * np<<endl;
- my_dp[cur][1] = ( my_dp[cur ^ 1][1 ^ cur_x] * p + my_dp[cur ^ 1][1] * np )%mod;
- my_dp[cur][0] = (my_dp[cur^1][0 ^ cur_x] * p + my_dp[cur^1][0] * np )%mod;
- dout <<i <<" : "<<my_dp[cur][0] <<" "<<my_dp[cur][1] <<" "<<cur_x<<endl;
- }
- ll x = (1<<bit);
- x = (x * x)%mod;
- ans += my_dp[n&1][1] * x;
- ans %= mod;
- }
- dout << ans<<endl;
- ll dp[2][2][2];
- for(int bit0 = 0;bit0 <= 29;++bit0){
- for(int bit1 = bit0+1;bit1 <= 29;++bit1){
- memset(dp,0,sizeof dp);
- dp[0][0][0] = 1;
- for(int i=1;i<=n;++i){
- int cur = (i&1);
- int cur_0 = 0;
- int cur_1 = 0;
- if(a[i]&(1<<bit0))
- cur_0 = 1;
- if(a[i]&(1<<bit1))
- cur_1 = 1;
- for(int i=0;i<2;++i){
- for(int j=0;j<2;++j){
- dp[cur][i][j] = (dp[cur ^ 1][i^cur_0][j^cur_1] * p + dp[cur^1][i][j] * np)%mod;
- }
- }
- }
- ll val = (1ll<<bit0) * (1ll<<bit1);
- val = val%mod;
- val = (val * 2)%mod;
- ans+= (val * dp[n&1][1][1] )%mod;
- }
- }
- ans%=mod;
- cout << ans<<"\n";
- }
- int main(){
- #ifdef zxc
- debug = 1;
- freopen("input.txt","r",stdin);
- #endif
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int t = 1;
- while(t--)
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement