3206232_mle.java

来自「北大大牛代码 1240道题的原代码 超级权威」· Java 代码 · 共 96 行

import java.util.*;
import java.math.*;

public class Main
{
	int n, k;
	int [] num;
	String [] str;
	String [] al;
	BigInteger tot;
	BigInteger [] pro;

	public static void main(String [] args)
	{
		new Main().run();
	}

	public void run()
	{
		int i, j;
		String a, b;
		Scanner cin = new Scanner (System.in);

		n = cin.nextInt();
		k = cin.nextInt();
		str = new String [k+1];
		al = new String [n+1];
		pro = new BigInteger [n+1];
		num = new int [n+1];
		for(i = 0; i < k; i++)
		{
			str[i] = cin.next();
		}
		for(i = 0; i < n; i++)
		{
			boolean [] used = new boolean [27];
			for(j = 0; j < k; j++)
			{
				if(!used[str[j].charAt(i)-'a'])
				{
					used[str[j].charAt(i)-'a'] = true;
					num[i]++;
				}
			}
			al[i] = "";
			for(j = 0; j < 26; j++)
			{
				if(!used[j])
				{
					al[i] += (char)(j+'a');
				}
			}
			num[i] = 26-num[i];
		}
		pro[n-1] = BigInteger.ONE;
		for(i = n-2; i >= 0; i--)
		{
			pro[i] = pro[i+1].multiply(BigInteger.valueOf(num[i+1]));
		}
		tot = pro[0].multiply(BigInteger.valueOf(num[0]));
		a = cin.next();b = cin.next();
		BigInteger ida, idb, id;
		ida = getId(a);
		idb = getId(b);
		id = ida.add(idb).mod(tot);
		System.out.println(find(id));
	}

	private String find(BigInteger id)
	{
		String ret;

		ret = "";
		for(int i = 0; i < n; i++)
		{
			int index = id.divide(pro[i]).intValue();
			ret += al[i].charAt(index);
			id = id.mod(pro[i]);
		}
		return ret;
	}

	private BigInteger getId(String s)
	{
		BigInteger ret;

		ret = BigInteger.ZERO;
		for(int i = 0; i < n; i++)
		{
			int index = al[i].indexOf(s.charAt(i));
			BigInteger tmp = BigInteger.valueOf(index);
			ret = ret.add(pro[i].multiply(BigInteger.valueOf(index)));
		}
		return ret;
	}
}