Submission #7513291

---

Source Code Expand

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

map<int, double> memo;

double comb(int a, int b){
    if(a < 2 * b) return comb(a, a-b);
    double res = 1;
    for(int i=a; i>a-b; i--){
        res *= i;
    }
    for(int i=2; i<=b; i++){
        res /= i;
    }
    return res;
}

double dfs(int N){
    if(N==1) return 0;
    if(N==2) return 3./2;
    if(memo.count(N)) return memo[N];
    double res = 0;
    for(int i=1; 2*i<=N; i++){
        if(2*i<N){
            res += 6 * comb(N, i) * dfs(i);
        }else if(2*i==N){
            res += 3 * comb(N, i) * dfs(i);
        }
        for(int j=i; 1 <= N-i-j; j++){
            auto k = N - i - j;
            if(k < j) continue;
            if(k == i) continue;
            auto c = 6 * comb(N, i) * comb(N-i, j);
            if(i==j) c /= 2;
            if(j==k) c /= 2;
            res += c * dfs(i);
        }
    }
    res = 1 + res / pow(3, N);
    double p = 3;
    if(N%3==0){
        p += comb(N, N/3) * comb(N-N/3, N/3);
    }
    p /= pow(3, N);
    res /= 1-p;
    memo[N] = res;
    return res;
}

int main()
{
    int N;
    cin >> N;
    cout<<setprecision(10)<< dfs(N) << endl;;

    return 0;
}

Submission Info

Judge Result