Readme

3518.Smallest-Palindromic-Rearrangement-II

很明显本题的核心就是，我们取原字符串前一半的字母，问这些字母所能组成的从小到大的第k个字典序的排列是什么。因为有重复的字符，这里要求重复的排列只算一种。

关于n个字母的排列，求第k大的字典序，是一个比较常规的题目了。我们只需要从按头到尾的顺序、把候选字母从小到大地进行尝试即可。比如说，我们尝试第一个位置填写a，并且计算出后面n-1个位置如果有m种排列，那么就可以根据m和k的大小关系进行决策：如果m<k，那么说明第一个位置填写a是不够的，那么我们就可以尝试填写b（或者其他更大的候选字符）；如果m>=k，那么我们就能确定第一个位置必然是a，此时进行递归处理第二个位置即可。

由此，我们需要一个函数countPermutations(vector<int>&nums)，表示给定一系列字母及其个数的情况下，有多少种不同的排列。其中nums是一个长度为26的数组，记录每种字符的个数。假设总共的字符个数是n。此时最容易想到的算法就是 count = n!/(t0!)*(t1!)...*(t25!)，其中ti表示每种字符的个数。因为n达到了1e4，其阶乘是天文数字，必然会溢出；并且这涉及到了大数的除法，我们无法保证精度。此时就应该想到第二种算法，就是 count = C(n,t0)*C(n-t0,t1)*C(n-t0-t1,t2)*...这里就规避了除法的精度问题，但是溢出问题依然得不到解决。

此时注意到k不超过1e6。一旦count的计算需要涉及到超大的阶乘数，那么必然会远远超过k。当这种情况发生时，我们其实并不需要知道count的精确数值，因为根据之前的说法，我们对字母选择的决策其实是很明显的了。因此我们在计算count甚至在计算组合数本身时，如果能预期到它很大，我们直接就返回INT_MAX/2之类的超大数来影响决策即可，而不需要计算它实际的数值。

此外，本题对于空间的利用需要达到极致。我们知道，可以用n^2的时间和空间来提前处理Comb(n,x)级别的组合数。通常我们只能开到comb[1000][1000]的规模。但是利用到C(m,n)=C(m,m-n)的性质，我们可以最大开辟数组空间达到comb[5001][2501]。代码如下：

    int comb[5001][2501];  
    int getComb(int m, int n)
    {
        if (m<n) return 0;
        if (n<=(m+1)/2)
            return comb[m][n];
        else
            return comb[m][m-n];
    }
    void precompute(int n)
    {        
        for (int i = 0; i <= n; ++i) 
        {
            comb[i][0] = 1;
            if (i==0) continue;
            for (int j = 1; j <= (i+1)/2; ++j) 
            {
                comb[i][j] = getComb(i-1, j-1) + getComb(i-1,j);
                comb[i][j] = min(comb[i][j], INT_MAX/2);
            }
        }
    }