Codeforces Gym10081 A.Arcade Game-康托展开、全排列、组合数变成递推的思想

最近做到好多概率，组合数，全排列的题目，本咸鱼不会啊，我概率论都挂科了。。。

这个题学到了一个康托展开，有点用，瞎写一下。。。

康托展开:

适用对象:没有重复元素的全排列。

把一个整数X展开成如下形式：

X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[2]*1!+a[1]*0![1]

其中a[i]为当前未出现的元素中是排在第几个（从0开始），并且0<=a[i]<i(1<=i<=n)

用来求全排列中这个串排第几，康托展开的逆运算就是找排名第n个的是什么。。。

传送门，懒得写，都差不多 1.(｡･ω･｡)   2.( • ̀ω•́ )✧   3.٩(๑❛ᴗ❛๑)۶   4.٩(๑>◡<๑)۶ 

直接上题目:

A .Arcade Gam

Arcade mall is a new modern mall. It has a new hammer game called "Arcade Game". In this game you're presented with a number n which is hanged on a wall on top of a long vertical tube, at the bottom of the tube there is a button that you should hit with your hammer.

When you hit the button with all your force (as you always do), a ball is pushed all over the tube and hit the number n. The number n flies in the air and it's digits fall back in any random permutation with uniform probability.

If the new number formed is less than or equal to the previous number, the game ends and you lose what ever the new number is. Otherwise (if the number is greater than the previous number), you are still in the game and you should hit the button again.

You win if the new number formed is greater than the previous number and it is equal to the greatest possible permutation number.

Can you compute the probability of winning?

Input

The first line of the input contains the number of test cases T. Following that there are T lines represents T test cases. In each line, there is a single integer (1 ≤ n ≤ 10⁹) the target number. The digits of n are all unique, which means that any 2 digits of n are different.

Output

For each test case, print one line containing the answer. Print the answer rounded to exactly 9 decimal digits.

Example

Input

3
952
925
592

Output

0.000000000
0.166666667
0.194444444

Note

In the first test case, the answer is 0 because 952 is greater than all 2,5 and 9 permutations so you can't win, whatever you do.

In the second test case, the answer is 0.166666667 because you may win by getting number 952 with probability 1/6.

In the third test case the answer is 0.194444444 because you may win by getting number 952 in round1 with probability 1/6 or you can win by getting number 925 in round 1 and then 952 in round 2 with probability 1/6 * 1/6.

这个题就是找出来之后求概率，这里求概率是把符合条件的都加进去，假设10个数，每个数被跳到的概率都是1/10，为P。

假设你要求的是排名第5，那么排名第5的跳到排名第1的有很多种跳法。可以直接跳到第一大，也可以跳2步，也可以跳3步，也可以跳4步。因为最后都是要跳到最大的，所以只求中间的步数的概率就可以，所以就是排列组合的问题，就是P*C(1,1)+P^2*C(1,3)+P^3*C(2,3)+P^4*C(3,3)。但是如果按组合数写的话，会超时，这里把组合数优化一下，写成递推就可以了，极限操作最大就是10^9，而不是(10^9+1)*10^9/2次操作。就是从n^2d的操作变成n的操作，但是递推怎么想呢。

抽抽一下，发现，跳1步为0,从第2大跳到第1大赢的概率就是Q1=P,从第3大开始跳获胜的概率就是Q2=P+P*Q1=Q1*(1+P)，从第4大开始跳获胜的概率就是Q3=P+P*Q2+P*Q1=Q2*(1+P),从第5大开始跳获胜的概率就是Q4=P+P*Q3+P*Q2+P*Q1=Q3*(1+P)。写的乱七八糟，不知道能不能看懂。。。

代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1e7+10;
typedef long long ll;
ll fac[N];
bool cmp(char a,char b){
    return a>b;
}
void factorial(){     //阶乘
    fac[0]=1;
    for(int i=1;i<10;i++){
        fac[i]=fac[i-1]*i;
    }
}
int cantor(char s[],int n){    //康托展开
    int cnt,sum;
    sum=0;
    factorial();
    for (int i=0;i<n;++i){
        cnt=0;
        for(int j=i+1;j<n;++j)
            if(s[j]<s[i])++cnt;
        sum+=cnt*fac[n-i-1];
    }
    return sum;
}
char s[N];
double ans[N];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        memset(s,0,sizeof(s));
        scanf("%s",s);
        int len=strlen(s);
        int num1=cantor(s,len)+1;   //该数的排名，第几大
        //cout<<num1<<endl;
        sort(s,s+len,cmp);
        int num2=cantor(s,len)+1;   //最大的数的排名就是全排列一共多少个数
        //cout<<num2<<endl;
        double gailv=1.0/num2;
        //cout<<gailv<<endl;
        //cout<<num2-num1<<endl;
        ans[0]=0;ans[1]=gailv;
        for(int i=2;i<=num2-num1;i++){  //递推
            ans[i]=ans[i-1]*(1+gailv);
        }
        printf("%.9f
",ans[num2-num1]);
    }
    return 0;
}

太智障了，好蠢啊。。。