3206465_tle.java

北大大牛代码 1240道题的原代码 超级权威

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

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

	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];
		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];
		}
		tot = BigInteger.ONE;
		for(i = n-1; i >= 0; i--)
		{
			tot = tot.multiply(BigInteger.valueOf(num[i]));
		}
		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 = n-1; i >= 0; i--)
		{
			int index = id.mod(BigInteger.valueOf(num[i])).intValue();
			ret += al[i].charAt(index);
			id = id.divide(BigInteger.valueOf(num[i]));
		}
		String tmp;
		tmp = "";
		for(int i = ret.length()-1; i >= 0; i--)
		{
			tmp += ret.charAt(i);
		}
		return tmp;
	}

	private BigInteger getId(String s)
	{
		BigInteger ret, last;

		ret = BigInteger.ZERO;
		last = BigInteger.ONE;
		for(int i = n-1; i >= 0; i--)
		{
			int index = al[i].indexOf(s.charAt(i));
			BigInteger tmp = BigInteger.valueOf(index);
			ret = ret.add(last.multiply(tmp));
			last = last.multiply(BigInteger.valueOf(num[i]));
		}
		return ret;
	}
}