【题目链接】:http://oj.acmclub.cn/problem.php?cid=1164&pid=0

【题意】

【题解】



把每个数字都%3处理;

会发现最后1的个数为n+1

2和0的个数都为1

也就是说2的个数比1的个数要少1个;

这样;我们先不用考虑0;

因为它对%3的结果不会造成影响;

这里先考虑开头是2的情况

假设我们放了一个2在开头;

则我们只能再放一个2了;

即22

因为不能21吧

那然后呢

现在为22

->%3==1

接下来不能放2了;

只能放1

即

221

然后%3==2

又放2

->2212

->%3==1

这里可以发现,只能1，2，1，2地放了

我们这里再放一个1的话

22121

会发现,1的个数永远比2的个数少1个;

也就是说,在某个时刻,需要2的时候,没有2了,只剩下1了!??

那么就无解了!!

所以开头不能为2

那么只能为1了

既然开头为1

即

->1

然后只能再放1了

->11

然后

->112

会发现%3==1

这个时候只能再放1

->1121

可以发现只能是

->112121212

这时可以发现,放完2之后,1总是比2多一个;

而这是可行的!

所以1和2的位置是确定的;

只是要放哪些数字的问题了;

然后在3*n个位置中(开头不能放0)选n个位置放0;

结果就为

A(3n,n)∗A(n,n)∗A(n+1,n+1)/A(3n+1,3n+1)

化简一下可以变成

n!/((n+2)∗(n+3)∗...∗2n∗(3n+1))



【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0),cin.tie(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 110;

double ans;

int k;

int main(){

    //Open();

    Close();

    cin >> k;

    while (k--){

        int n;

        cin >> n;

        ans = 1;

        rep1(i,1,n) ans = ans*i;

        rep1(i,n+2,2*n) ans/=i;

        ans/=(3*n+1);

        cout << fixed << setprecision(9) << ans << endl;

    }

    return 0;

}