链接：https://www.nowcoder.com/acm/contest/116/F

来源：牛客网

题目描述

我们知道有一种神奇的排序方法叫做猴子排序，就是把待排序的数字写在卡片上，然后让猴子把卡片扔在空中，等落下的时候观察这些卡片是否从左到右已经排序完成（我们认为不会发生卡片落地后叠在一起的情况）如果有序则排序完成，否则让猴子再扔一遍，直到卡片有序，那么问题来了，给你N个卡片，每个卡片上写着一个大写字母，请问猴子第一次扔这些卡片就按字典序排序完成的概率有多大?

输入描述:

第一行是一个整数N(1<N<100)表示给猴子N张卡片，接下来是一个长度为N的字符串，代表这些卡片上所写的字母。

输出描述:

输出一行，表示猴子排序第一次就成功的概率(用分子为1的分数表示)。

示例1

输入

7

SCIENCE

输出

1/1260

//这个代码找到错了，居然是string输入不能用nextLine而要用next？？？我r

【分析】：分母为A(n,n)/字符串中多次出现的字符出现次数的阶乘=n！/ (k1! * k2! * ...)

首先，next（）一定要读取到有效字符后才可以结束输入，对输入有效字符之前遇到的空格键、Tab键或Enter键等结束符，next（）方法会自动将其去掉，只有在输入有效字符之后，next（）方法才将其后输入的空格键、Tab键或Enter键等视为分隔符或结束符。简单地说，next（）查找并返回来自此扫描器的下一个完整标记。完整标记的前后是与分隔模式匹配的输入信息，所以next方法不能得到带空格的字符串而nextLine（）方法的结束符只是Enter键，即nextLine（）方法返回的是Enter键之前的所有字符，它是可以得到带空格的字符串的。###

import java.util.HashMap;

import java.util.Map;

import java.util.Scanner;

import java.io.*;

import java.math.*;

public class Main{

	public static BigInteger fun(int n){

		BigInteger num = BigInteger.ONE;

		for(int i=1;i<=n;i++)

			num=num.multiply(BigInteger.valueOf(i));

        return num;

	}

//7 SCIENCE

//1/1260

	public static void main(String[] args) {

		   Scanner cin = new Scanner(System.in);

		   int n = cin.nextInt();

		   String s = cin.nextLine(); //！！！！！！改成next（）

		   char[] a=s.toCharArray();

		   Map<Character, Integer> map = new HashMap<Character,Integer>();  

		   BigInteger pro = fun(n);

		   //System.out.println(pro);

		   for(char c : a)

		   {//记录每个字符出现次数,若未出现初始化为1,否则不断+1

			   map.put(c, !map.containsKey(c)?1:(map.get(c)+1));

		   }

		   //遍历map,map.get(key)是得到键所对应的值

		   for(Character key : map.keySet()) {

	            //System.out.println(key + "=" + map.get(key));

	            if(map.get(key)>1) {

	            	pro = pro.divide(fun(map.get(key)));

	            }

	        }

		   System.out.print(1);

		   System.out.print("/");

		   System.out.println(pro);

		}

	}

不用map用hash

import java.io.*;

import java.util.*;

import java.util.Scanner;

import java.math.BigInteger;

import java.lang.*;

public class Main{

	static BigInteger fun(int n){

		BigInteger num = BigInteger.ONE;

		for(int i=2; i<=n; i++)

			num = num.multiply(BigInteger.valueOf(i));

        return num;

	}

	public static void main(String[] args) {

		   Scanner cin = new Scanner(System.in);

		   int n = cin.nextInt();

		   String s = cin.next();

		   int[] arr = new int[500];

		   for(int i=0; i<s.length(); i++) {

			   arr[s.charAt(i)-'A']++;

		   }

		   BigInteger pro = fun(n);

		   for(int i=0;i<500;i++) {

			   if(arr[i]!=0) {

				   pro = pro.divide(fun(arr[i]));

			   }

		   }

		   System.out.println("1/"+pro);

		}

	}

//7 SCIENCE

//1/1260