Submission #6904960

---

Source Code Expand

import java.util.*;

/**
 * @author masayamatu
 * 
 */
public class Main {


  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    List<List<Integer>> a = getPermutations(n-1);
    int[] c = new int[n];
    int[][] allcase = new int[factorial(n)][n];
    coin[][] allcasebf = new coin[factorial(n)][n];
    double ans = 0;
    for(int i = 0; i < n; i++) {
      c[i] = sc.nextInt();
    }
    for(int i = 0; i < factorial(n) ; i++) {
      int count = 0;
      for(int j = 0; j < n; j++) {
        allcase[i][j] = c[a.get(i).get(j)]; 
        allcasebf[i][j] =new coin(allcase[i][j],true);
      }
     coin.reverse(i,n,allcasebf);
     for(int j=0; j < n; j++) {
       if(allcasebf[i][j].fb == true ) {
         count++;
       }
     }
     ans += (double)count/(double)factorial(n);
    }
    System.out.println(ans);
    
   
    
    
  }
  public static class coin {
    int coinnum = 0;
    boolean fb = true;
      public coin(int coinnum, boolean fb) {
        this.coinnum = coinnum;
        this.fb=fb;
      }
      public static void reverse(int facto,int n ,coin coin[][]) {
        for(int i = 0; i < coin.length-1; i++) {
          for(int j = i+1; j < n; j++) {
            if(coin[facto][j].coinnum % coin[facto][i].coinnum == 0) {
              if( coin[facto][j].fb == false) {
                coin[facto][j].fb = true;
              } else {
                coin[facto][j].fb = false;
              }
            }
          }
        }
        
      }
  }
  private static List<List<Integer>> getPermutations(Integer n){
    if(n == null || n<0) {
      return null;
    }
    List<List<Integer>> results = new ArrayList<List<Integer>>();
    
    if(n == 0) {
      results.add(new ArrayList<Integer>(Arrays.asList(0)));
      return results;
    }
    List<List<Integer>> prevResults = getPermutations(n-1);
    
    for(List<Integer> permutation : prevResults) {
      for(int i = 0; i <= n; i++) {
        permutation.add(i,n);
        results.add(new ArrayList<Integer>(permutation));
        permutation.remove(n);
      }
      permutation.clear();
    }
    prevResults.clear();
    
    return results;
  }
  public static int factorial(int b) {
    if(b == 1) {
      return 1;
    }else {
      return b*factorial(b-1);
    }
  }
}

Submission Info

Judge Result