This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// 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; }