結果
問題 | No.248 ミラー君の宿題 |
ユーザー | anta |
提出日時 | 2015-07-18 00:06:38 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 611 ms / 5,000 ms |
コード長 | 3,662 bytes |
コンパイル時間 | 680 ms |
コンパイル使用メモリ | 84,464 KB |
実行使用メモリ | 4,380 KB |
最終ジャッジ日時 | 2023-09-22 18:35:34 |
合計ジャッジ時間 | 5,042 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 8 ms
4,376 KB |
testcase_01 | AC | 6 ms
4,376 KB |
testcase_02 | AC | 7 ms
4,380 KB |
testcase_03 | AC | 9 ms
4,380 KB |
testcase_04 | AC | 22 ms
4,380 KB |
testcase_05 | AC | 25 ms
4,380 KB |
testcase_06 | AC | 50 ms
4,376 KB |
testcase_07 | AC | 85 ms
4,380 KB |
testcase_08 | AC | 9 ms
4,376 KB |
testcase_09 | AC | 331 ms
4,376 KB |
testcase_10 | AC | 299 ms
4,376 KB |
testcase_11 | AC | 149 ms
4,376 KB |
testcase_12 | AC | 231 ms
4,376 KB |
testcase_13 | AC | 326 ms
4,376 KB |
testcase_14 | AC | 493 ms
4,380 KB |
testcase_15 | AC | 524 ms
4,376 KB |
testcase_16 | AC | 611 ms
4,376 KB |
testcase_17 | AC | 97 ms
4,376 KB |
ソースコード
#include <string> #include <vector> #include <algorithm> #include <numeric> #include <set> #include <map> #include <queue> #include <iostream> #include <sstream> #include <cstdio> #include <cmath> #include <ctime> #include <cstring> #include <cctype> #include <cassert> #include <limits> #include <functional> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i)) #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i)) #if defined(_MSC_VER) || __cplusplus > 199711L #define aut(r,v) auto r = (v) #else #define aut(r,v) __typeof(v) r = (v) #endif #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it) #define all(o) (o).begin(), (o).end() #define pb(x) push_back(x) #define mp(x,y) make_pair((x),(y)) #define mset(m,v) memset(m,v,sizeof(m)) #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL using namespace std; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pair<int,int> > vpii; typedef long long ll; template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; } template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; } //phi(P) | Q //r^Q = 1 //p_i - 1 = 2^{e_i} × q_i //p_i | h //p_i | (c - 1) //c ≡ 1 (mod p_i) //max_j {f_j(r)} = f_i(r) // { a^{2^k} = 1 | a <- S } //= { 2^k×l ≡ 0 (mod p-1) | l <- [0..p-2] } //= { v_2(l) >= v_2(p-1) - k | l <- [0..p-2] } //= (p-1) / 2^{max(0, v_2(p-1) - k)} // int main() { int T; scanf("%d", &T); rep(ii, T) { int N; scanf("%d", &N); vector<long long> P(N); rep(i, N) scanf("%lld", &P[i]); vector<int> v_2(N); rep(i, N) { long long x = P[i] - 1; int k = 0; while(x % 2 == 0) x /= 2, ++ k; v_2[i] = k; } int maxv2 = *max_element(all(v_2)); vector<double> dp(1 << N); dp[0] = 1; rep(i, N) dp[1 << i] = 1; static double dp2[1 << 13]; static int masks[1 << 13]; vi is; rep(s, 1 << N) if((s & (s-1)) != 0) { is.clear(); rep(i, N) if(s >> i & 1) is.push_back(i); int n = is.size(); rep(t, 1 << n) { int u = 0; rep(ix, n) if(t >> ix & 1) u |= 1 << is[ix]; masks[t] = u; } double multgroupfailprob = 0; double multgroupsum = 0; rer(k, 0, maxv2) { rep(t, 1 << n) dp2[t] = 0; dp2[0] = 1; rep(ix, n) { int v = v_2[is[ix]]; //1 / 2^{max(0, v_2[i] - k)} double prob1 = 1. / (1LL << max(0, v - k)); double prob2 = k == 0 ? 0 : 1. / (1LL << max(0, v - (k - 1))); rep(t, 1 << ix) { double x = dp2[t]; if(x < 1e-99) continue; dp2[t] = x * prob2; dp2[t | 1 << ix] = x * (prob1 - prob2); } } multgroupfailprob += dp2[(1 << n)-1]; reu(t, 1, (1 << n)-1) { double x = dp2[t]; if(x < 1e-99) continue; int u = masks[t]; multgroupsum += x * (dp[u] + dp[s - u]); } } //dp2[t] = t が 0 になる確率 rep(t, 1 << n) dp2[t] = 0; dp2[0] = 1; rep(ix, n) { long long p = P[is[ix]]; double prob = 1. / p; rep(t, 1 << ix) { double x = dp2[t]; if(x < 1e-99) continue; dp2[t] = x * (1 - prob); dp2[t | 1 << ix] = x * prob; } } double total = 0, failprob = 0; reu(t, 1, (1 << n)-1) { int u = masks[t]; total += dp2[t] * (dp[u] + dp[s - u]); } failprob += dp2[(1 << n)-1]; total += dp2[0] * multgroupsum; failprob += dp2[0] * multgroupfailprob; //E = 1 + failprob * E + total //E = (1 + total) / (1 - failprob) dp[s] = (1 + total) / (1 - failprob); // cerr << s << ": " << dp[s] << ", " << failprob << ", " <<total << endl; } double ans = dp[(1 << N)-1]; printf("%.10f\n", ans); } return 0; }