結果
問題 | No.248 ミラー君の宿題 |
ユーザー |
![]() |
提出日時 | 2020-07-21 06:15:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 875 ms / 5,000 ms |
コード長 | 1,949 bytes |
コンパイル時間 | 1,768 ms |
コンパイル使用メモリ | 124,044 KB |
最終ジャッジ日時 | 2025-01-12 01:26:05 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; void solve(){ int n; cin>>n; ll p[15]; int e[15]={}; for(int i=0; i<n; i++){ cin>>p[i]; ll x=p[i]-1; while((x&1)==0){ e[i]++; x>>=1; } } double dp[1<<13]; double a[64][1<<13], b[64][1<<13]; for(int t=0; t<64; t++){ for(int i=1; i<(1<<n); i++){ a[t][i]=1; for(int j=0; j<n; j++){ if(i&(1<<j)){ if(e[j]<t){ a[t][i]=0; break; } if(t) a[t][i]*=(double)(1ll<<(t-1)); } } if(t==0){ b[t][i]=0; continue; } b[t][i]=1; for(int j=0; j<n; j++){ if(i&(1<<j)){ b[t][i]*=(double)(1ll<<min(t-1, e[j])); } } } } for(int i=1; i<(1<<n); i++){ if(popcount(i)==1){ dp[i]=1; continue; } double sum=0; for(int j=i; j>0; j=(j-1)&i){ if(j==i) continue; double q=1; for(int k=0; k<n; k++){ if(j&(1<<k)) q*=(double)(p[k]-1); } sum+=q*(dp[j]+dp[i^j]); } double q0=1, q1=1; for(int j=0; j<n; j++){ if(i&(1<<j)){ q0*=(double)p[j], q1*=(double)((p[j]-1)>>e[j]); } } double sum1=q0-1, q2=0; for(int t=0; t<64; t++){ if(a[t][i]<0.1) break; q2+=a[t][i]; } sum1-=q2*q1; for(int j=i; j>0; j=(j-1)&i){ if(j==i) continue; double q=0; for(int t=1; t<64; t++){ if(a[t][j]<0.1) break; q+=a[t][j]*b[t][i^j]; } sum+=q*q1*(dp[j]+dp[i^j]); } dp[i]=(sum+q0)/sum1; } printf("%.9lf\n", dp[(1<<n)-1]); } int main() { int t; cin>>t; while(t--) solve(); return 0; }