企业官网建设流程全解析

题目描述

字符串的排列是指将其所有字符重新组合得到的所有可能字符串的集合。例如，abc的排列集合为 {abc,acb,bac,bca,cab,cba}，该集合的大小等于初始字符串长度的阶乘。

给定一个字符串SSS（长度最多为202020，且仅包含小写字母）以及一个整数NNN（0≤N<20!0 \le N < 20!0≤N<20!），要求找出SSS的所有排列中按字典序排序后的第(N+1)(N + 1)(N+1)个排列。注意，字符串SSS的初始顺序可能并非有序。

输入格式

输入文件的第一行包含一个整数，表示测试用例的数量。接下来每个测试用例由两行组成：第一行为字符串SSS，第二行为整数NNN。

输出格式

对于每个测试用例，输出一行，表示所要求的排列字符串。

样例输入

2 abc 3 abcde 119

样例输出

bca edcba

题目分析

本题要求求解给定字符串按字典序排序后的第(N+1)(N + 1)(N+1)个排列。由于字符串长度最多为202020，其全排列数量可达20!20!20!，远远超出直接枚举的可行范围，因此必须借助数学方法直接定位目标排列。

核心难点在于字符串中可能含有重复字符，此时不同排列的总数会小于20!20!20!，需要使用多重集排列公式进行修正。另外，NNN可以取到20!−120! - 120!−1量级，必须使用646464位整数进行存储与运算。题目还特别强调输入字符串不一定是已经排好序的，因此在开始求解前必须先将字符串排序，以保证后续按字典序递推的正确性。

解题思路

首先对字符串SSS进行升序排序，得到字典序最小的排列。记排序后字符串的长度为nnn，则理论上全排列数量为n!n!n!。由于存在重复字符，实际不同排列数为n!∏ccntc!\frac{n!}{\prod_{c} cnt_c!}∏c​cntc​!n!​，其中cntccnt_ccntc​为字符ccc在字符串中出现的次数。将NNN对实际排列总数取模后再加111，可将问题转化为求第N′N'N′个排列（1≤N′≤T1 \le N' \le T1≤N′≤T，TTT为不同排列总数）。

接下来采用逐位确定的策略。对于当前待处理的后缀字符串，设其长度为mmm，考虑将哪个字符放在当前位。枚举候选字符并按升序尝试，对于每个候选字符ccc，计算以ccc开头时剩余字符能形成的不同排列数PPP。若N′>PN' > PN′>P，说明目标排列不在以ccc开头的分支中，令N′←N′−PN' \leftarrow N' - PN′←N′−P并尝试下一个候选字符；若N′≤PN' \le PN′≤P，则确定当前位为ccc，输出该字符，并从剩余字符中移除一个ccc，继续确定下一位。

当剩余字符串长度为111时，直接输出该字符并结束。计算PPP时，同样需要考虑剩余字符中的重复情况，使用阶乘除以各字符出现次数的阶乘。该过程的时间复杂度为O(n2)O(n^2)O(n2)，空间复杂度为O(n)O(n)O(n)，对于n≤20n \le 20n≤20完全可行。

代码实现

// Permutations// UVa ID: 941// Verdict: Accepted// Submission Date: 2017-03-06// UVa Run Time: 0.280s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;longlongintfactor[21]={1};longlongintgetPermutations(string S){longlongintT=factor[S.length()];intt=0,c=0;for(inti=0;i<S.length();i++){if(c==S[i]){t++;continue;}if(t>0)T/=factor[t];t=1;c=S[i];}if(t>0)T/=factor[t];returnT;}voiddfs(string S,longlongintN){if(S.length()==1){cout<<S;return;}longlongintP=getPermutations(S.substr(1));if(N>P){for(intj=1;j<S.length();j++)if(S[j]>S[0]){swap(S[0],S[j]);break;}dfs(S,N-P);}else{cout<<S[0];if(N==P){for(intj=S.length()-1;j>0;j--)cout<<S[j];}else{dfs(S.substr(1),N);}}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intC;longlongintN;string S;for(inti=1;i<=20;i++)factor[i]=factor[i-1]*i;cin>>C;for(intcases=1;cases<=C;cases++){cin>>S>>N;sort(S.begin(),S.end());longlongintT=getPermutations(S);N%=T;N++;dfs(S,N);cout<<'\n';}return0;}

总结

本题的关键在于利用阶乘与多重集排列计数直接定位字典序第NNN个排列，避免了暴力枚举。实现时需注意以下要点：字符串必须先排序；排列总数需除以重复字符的阶乘进行修正；NNN需对实际排列总数取模后再加111，以统一处理NNN恰好为排列总数整数倍的情况；所有计数变量必须使用646464位整数。逐位确定时采用递归或迭代均可，时间复杂度为O(n2)O(n^2)O(n2)，空间复杂度为O(n)O(n)O(n)，能够高效处理长度不超过202020的字符串。