test/aoj/2446.test.cpp

• View this file on GitHub
• Last update: 2021-09-23 20:26:31+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2446

Depends on

• convolution/bitwise/fwht.cpp
• convolution/bitwise/or.cpp
• io/precision.cpp

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2446
// verification-helper: ERROR 1e-7

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../io/precision.cpp"
#include "../../convolution/bitwise/fwht.cpp"
#include "../../convolution/bitwise/or.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  using ll = long long;

  int n;
  ll m;
  cin>>n>>m;
  vector<ll> as(n),ps(n);
  for(int i=0;i<n;i++) cin>>as[i];
  for(int i=0;i<n;i++) cin>>ps[i];

  vector<ll> dp(1<<n,0);
  for(int bit=1;bit<(1<<n);bit++){
    ll t=1;
    for(int i=0;i<n;i++){
      if((~bit>>i)&1) continue;
      ll k=as[i]/gcd(t,as[i]);
      t=(t<=m/k?t*k:m+1);
      if(t>m) break;
    }
    dp[bit]=m/t;
  }

  fwht(dp,bitwise_or::moebius);

  double ans=0;
  for(int bit=0;bit<(1<<n);bit++){
    double po=1;
    for(int i=0;i<n;i++)
      if((bit>>i)&1) po*=ps[i]/100.0;
      else po*=1.0-(ps[i]/100.0);
    ans+=po*abs(dp[bit]);
  }
  cout<<ans<<endl;
  return 0;
}

#line 1 "test/aoj/2446.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2446
// verification-helper: ERROR 1e-7

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "io/precision.cpp"

#line 3 "io/precision.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
struct Precision{
  Precision(){
    cout<<fixed<<setprecision(12);
  }
}precision_beet;
//END CUT HERE
#ifndef call_from_test
signed main(){
  return 0;
}
#endif
#line 1 "convolution/bitwise/fwht.cpp"

#line 3 "convolution/bitwise/fwht.cpp"
using namespace std;
#endif
// https://kazuma8128.hatenablog.com/entry/2018/05/31/144519
//BEGIN CUT HERE
// O(n \log n)
template<typename T, typename F>
void fwht(vector<T> &as,F f){
  int n=as.size();
  for(int d=1;d<n;d<<=1)
    for(int m=d<<1,i=0;i<n;i+=m)
      for(int j=0;j<d;j++)
        f(as[i+j],as[i+j+d]);
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 1 "convolution/bitwise/or.cpp"

#line 3 "convolution/bitwise/or.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
namespace bitwise_or{
  auto zeta=[](auto& lo,auto& hi){hi+=lo;};
  auto moebius=[](auto& lo,auto& hi){hi-=lo;};
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 11 "test/aoj/2446.test.cpp"
#undef call_from_test

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  using ll = long long;

  int n;
  ll m;
  cin>>n>>m;
  vector<ll> as(n),ps(n);
  for(int i=0;i<n;i++) cin>>as[i];
  for(int i=0;i<n;i++) cin>>ps[i];

  vector<ll> dp(1<<n,0);
  for(int bit=1;bit<(1<<n);bit++){
    ll t=1;
    for(int i=0;i<n;i++){
      if((~bit>>i)&1) continue;
      ll k=as[i]/gcd(t,as[i]);
      t=(t<=m/k?t*k:m+1);
      if(t>m) break;
    }
    dp[bit]=m/t;
  }

  fwht(dp,bitwise_or::moebius);

  double ans=0;
  for(int bit=0;bit<(1<<n);bit++){
    double po=1;
    for(int i=0;i<n;i++)
      if((bit>>i)&1) po*=ps[i]/100.0;
      else po*=1.0-(ps[i]/100.0);
    ans+=po*abs(dp[bit]);
  }
  cout<<ans<<endl;
  return 0;
}

Back to top page