1529 排列与编码
给出两个长度为N的排列P1，P2，有着完全相同的元素。设这些元素所能组成的不同的排列数量共L个（L可能很大），按照字典序排序后，编码为 0 到 L - 1。其中P1的编码为R1，P2的编码为R2。求编码为：(R1 + R2) % L的排列是什么？
例如：P1 = {2, 2, 1}，P2 = {2, 1, 2}，则L = 3， R1 = 2, R2 = 1，那么需要求的排列编码为：(R1 + R2) % L = (2 + 1) % 3 = 0，对应的排列为：{1, 2, 2}。
输入
第1行：1个数N，表示排列的长度（1 <= N <= 50000）。
第2 -N + 1行：每行2个数，用空格分隔，对应P1[i]和P2[i]（1 <=P[i] <= 10^9)。
(输入数据保证P1同P2有着完全相同的元素)。输出
输出共n行，对应题目要求的排列。输入样例
3
2 2
2 1
1 2输出样例
1
2
2分析：
对于这个问题，我并没有想出优雅的方法，而是比较暴力的使用高精计算，因此你最好选择Java 8，Python，Ruby，Go等支持FFT高精的语言来解题（计算中需要用到高精除法）。
假如没有重复的话，直接使用康托展开（康托展开_百度百科）便可以处理，有重复的话需要将计算结果除以当前数字出现的次数，考虑到大数运算的复杂度，整个算法是平方的。所以我们考虑用混合进制来表示大数，但每一位都需要用高精来存储，以便好好利用FFT的优势。
混合进制的可选方案也很多，在某一位上甚至可以使用5/2这类进制（方便处理重复字符的情况），但考虑整个计算除了要计算编码，还要根据编码反向计算排列，按照这种方式，很难做到一致，所以需要考虑无论是正向还是反向，都可以处理的一种进制，用阶乘进制来表示。
阶乘进制的第n位表示(n - 1)!，假设这一位的数字为k，则表示k*(n - 1)!。
第一步：使用康托展开，利用线段树或树状数组处理前缀和，可以求出某个排列的混合进制表示。
例如：1 3 1 2 2 1，处理结果为：
0 4 0 1 0 0 （后面的数字中有多少个比当前数字小）
3 1 2 2 1 1 （当前数字共有多少个，1有3个，所以第一位是3，但处理到第3位，第2个1时，由于前面的1已经减去，只剩下2个，所以第3位是2）
有了这两个计数，就好计算编码了，最终的结果是：
0 * (1 ) * (1 * 2 * 2 * 1 * 3) +
0 * (1) * ( 2 * 2 * 1 * 3) +
1 * (1 * 2) * ( 2 * 1 * 3) +
0 * (1 * 2 * 3) * (1 * 3) +
4 * (1 * 2 * 3 * 4) * (3) +
0 * (1 * 2 * 3 * 4 * 5)
= 312
这里计算的实际上是真实R的12倍，312 = 12 * 26，因为采用这种阶乘进制，会让结果扩大(1 * 1 * 2 * 2 * 1 * 3) = 12倍。
当然，按照上面的方法来计算，考虑高精本身的复杂度，算法还是平方级的，因此我们需要进行分治，整个过程相当于把这样一个混合进制的大数，转为普通进制的大数。而进制转换的复杂度是n*log(n)^2的。
0 * (1 ) * (1 * 2 * 2 * 1 * 3) +
0 * (1) * ( 2 * 2 * 1 * 3) +
1 * (1 * 2) * ( 2 * 1 * 3) +
0 * (1 * 2 * 3) * (1 * 3) +
4 * (1 * 2 * 3 * 4) * (3) +
0 * (1 * 2 * 3 * 4 * 5)
变为:
(0 * (1 ) * (1 * 2) +
0 * (1) * ( 2) +
1 * (1 * 2) )
* ( 2 * 1 * 3) +
(1 * 2 * 3) *
(0 * (1 * 3) +
4 * (4) * (3) +
0 * (4 * 5))
然后递归处理。这样计算可以让复杂度变为nlogn^2（因为大数运算的两边数值大小相近，FFT的效果最好）。
放Java代码：
import java.math.BigInteger;
import java.io.*;
import java.util.*;
public class Program
{
public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in), 1 << 12);
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out), 1 << 12);
int n = Integer.parseInt(reader.readLine());
int[] n1 = new int[n];
int[] n2 = new int[n];
DataServer data = new DataServer();
data.Init(n);
for(int i = 0; i < n; i++)
{
String[] input = reader.readLine().split(" ");
n1[i] = Integer.parseInt(input[0]);
n2[i] = Integer.parseInt(input[1]);
}
Integer[] result = data.Solve(n1, n2);
for(int i = 0; i < n; i++)
writer.write(result[i] + "\r\n");
writer.flush();
}
static class SegResult { public BigInteger Mul, Dig;}
static class Pair { public int Value, Rank;}
static class DataServer
{
public int[] DegTable, Tree, Counter;
public BigInteger[][] BaseTable;
public void Init(int n)
{
int maxDeep = 1, t = 1;
DegTable = new int[n + 1];
DegTable[1] = -1;
for (int i = 1; i <= n; i *= 2)
{
for (int j = i + 1; j <= i * 2 && j <= n; j++)
DegTable[j] = maxDeep - 1;
maxDeep++;
}
BaseTable = new BigInteger[maxDeep][];
for(int i = 0; i < BaseTable.length; i++)
{
int len = n / t + (n % t == 0 ? 0 : 1);
BaseTable[i] = new BigInteger[len];
t <<= 1;
}
GenBaseTable(0, n - 1);
}
public BigInteger GenBaseTable(int s, int e)
{
if (s == e)
SetBaseValue(s, e, BigInteger.valueOf(s + 1));
else
{
int len = 1 << DegTable[e - s + 1];
SetBaseValue(s, e, GenBaseTable(s, s + len - 1).multiply(GenBaseTable(s + len, e)));
}
return GetBaseValue(s, e);
}
public Pair[] GenPairs(int[] nums)
{
Pair[] pairs = new Pair[nums.length];
for (int i = 0; i < nums.length; i++)
{
pairs[i] = new Pair();
pairs[i].Value = nums[i];
}
return pairs;
}
public Integer[] Solve(int[] n1, int[] n2)
{
int n = n1.length, maxRank = 0;
Pair[] p1 = GenPairs(n1);
Pair[] p2 = GenPairs(n2);
SegResult rank1 = GetRank(p1);
SegResult rank2 = GetRank(p2);
for (int i = 0; i < n; i++)
maxRank = p1[i].Rank > maxRank ? p1[i].Rank : maxRank;
int[] rankToNum = new int[maxRank + 1];
int[] tree = new int[maxRank + 1];
int[] counter = new int[maxRank + 1];
for (int i = 0; i < n; i++)
{
Pair cur = p1[i];
rankToNum[cur.Rank] = cur.Value;
Add(cur.Rank, 1, tree);
counter[cur.Rank]++;
}
BigInteger dig = rank1.Dig.add(rank2.Dig);
if(dig.compareTo(BaseTable[BaseTable.length - 1][0]) >= 0)
dig = dig.subtract(BaseTable[BaseTable.length - 1][0]);
List<Integer> digs = new ArrayList<Integer>();
Tree = tree; Counter = counter;
GetRankInv(0, n - 1, dig, digs);
Integer[] result = digs.toArray(new Integer[0]);
for (int i = 0; i < n; i++)
result[i] = rankToNum[result[i]];
return result;
}
public SegResult GetRank(Pair[] pairs)
{
Pair[] pairsBak = (Pair[])pairs.clone();
Arrays.sort(pairsBak, new Comparator<Pair>()
{
public int compare(Pair a, Pair b) {return a.Value - b.Value;}
});
pairsBak[0].Rank = 1;
int n = pairsBak.length;
for (int i = 1; i < n; i++)
pairsBak[i].Rank = pairsBak[i - 1].Rank + (pairsBak[i].Value == pairsBak[i - 1].Value ? 0 : 1);
int maxRank = pairsBak[n - 1].Rank + 1;
int[] tree = new int[maxRank];
int[] counter = new int[maxRank];
int[] digs = new int[n];
int[] muls = new int[n];
for (int i = n - 1; i >= 0; i--)
{
Pair cur = pairs[i];
counter[cur.Rank]++;
int index = n - i - 1;
digs[index] = Query(cur.Rank - 1, tree);
Add(cur.Rank, 1, tree);
muls[(index - 1 + n) % n] = counter[cur.Rank];
}
return GetRank(muls, digs, 0, n - 1);
}
public BigInteger GetBaseValue(int s, int e)
{
int deep = DegTable[e - s + 1] + 1;
return BaseTable[deep][s >> deep];
}
public void SetBaseValue(int s, int e, BigInteger value)
{
int deep = DegTable[e - s + 1] + 1;
BaseTable[deep][s >> deep] = value;
}
public SegResult GetRank(int[] muls, int[] digs, int s, int e)
{
if (s == e)
{
SegResult result = new SegResult();
result.Mul = BigInteger.valueOf(muls[s]);
result.Dig = BigInteger.valueOf(muls[s] * digs[s]);
return result;
}
int len = 1 << DegTable[e - s + 1];
SegResult sR = GetRank(muls, digs, s, s + len - 1);
SegResult eR = GetRank(muls, digs, s + len, e);
SegResult result = new SegResult();
result.Mul = sR.Mul.multiply(eR.Mul);
result.Dig = sR.Dig.multiply(eR.Mul).add(eR.Dig.multiply(GetBaseValue(s, s + len - 1)));
return result;
}
public SegResult GetRankInv(int s, int e, BigInteger dig, List<Integer> ranks)
{
if (s == e)
{
int pre = dig.intValue() + 1;
int min = 1, max = Tree.length;
while (min != max)
{
int mid = (min + max) >> 1;
int count = Query(mid, Tree);
if (count < pre)min = mid + 1;
else max = mid;
}
SegResult result = new SegResult();
int preCount = Query(min - 1, Tree);
result.Dig = dig.subtract(BigInteger.valueOf(preCount));
result.Mul = BigInteger.valueOf(Counter[min]);
Counter[min]--;ranks.add(min);
Add(min, -1, Tree);
return result;
}
else
{
int len = 1 << DegTable[e - s + 1];
BigInteger lBase = GetBaseValue(s, s + len - 1);
BigInteger[] div1 = dig.divideAndRemainder(lBase);
SegResult rightRe = GetRankInv(s + len , e, div1[0], ranks);
div1[1] = div1[1].add(rightRe.Dig.multiply(lBase));
BigInteger[] div2 = div1[1].divideAndRemainder(rightRe.Mul);
SegResult leftRe = GetRankInv(s, s + len - 1, div2[0], ranks);
SegResult result = new SegResult();
result.Dig = div2[1].add(leftRe.Dig.multiply(rightRe.Mul));
result.Mul = rightRe.Mul.multiply(leftRe.Mul);
return result;
}
}
public void Add(int index, int value, int[] tree)
{
while (index < tree.length)
{
tree[index] = tree[index] + value;
index += (index & -index);
}
}
public int Query(int index, int[] tree)
{
int result = 0;
while (index > 0)
{
result += tree[index];
index -= (index & -index);
}
return result;
}
}
}