ThePreliminaryContestforICPCAsiaShanghai2019F.Rhymescheme——DP

This way

题意&＃xff1a;

题意不好说&＃xff0c;反正就是你需要构造一个长度为n的序列&＃xff0c;并且每个字符的大小最多是前面出现的最大的字符&＃43;1&＃xff0c;也就是说ABC是被允许的&＃xff0c;但是ACB是不被允许的&＃xff0c;因为C之前没有出现过B&＃xff0c;现在问你字典序第k大的是多少。

题解&＃xff1a;

有点像康托展开&＃xff0c;因为我们做到第i位的时候需要知道后面能够取到多少种情况&＃xff0c;那么我们用dp[i][j]表示当前数为i的时候&＃xff0c;后面有j位的情况数。
那么状态转移方程就是$dp[i][j]\&＃61;i\ast dp[i][j-1]\&＃43;dp[i\&＃43;1][j-1]$
因为我们在这一位是1-j的时候&＃xff0c;可以当做这一位是j&＃xff0c;因为下一位可以最大到第j&＃43;1位&＃xff0c;也就是说&＃xff0c;你后面能取的值的范围是从前面的最大的数决定的&＃xff0c;而不是当前的数&＃xff0c;当下一位取到i&＃43;1的时候&＃xff0c;最大数就变成了i&＃43;1。
然后我们一位一位做&＃xff0c;对于第i位的时候&＃xff0c;我们之后能够取到的最大值当然是前面出现的最大的值的情况&＃xff0c;也就是说ABCA的时候&＃xff0c;下一位能够出现的最大的值是D&＃xff0c;所以我们需要维护一个最大值&＃xff0c;然后判一下情况数够不够即可。
注意它的情况数最大可以达到4e19&＃43;&＃xff0c;所以需要用__int128.JAVA的大数会T&＃xff0c;可能是不够优秀吧。

#include
using namespace std;
__int128 dp[30][30];
int ans[30];
char s[30];
int main()
{dp[26][1]&＃61;26,dp[26][0]&＃61;1;for(int j&＃61;25;j;j--)dp[j][1]&＃61;j&＃43;1,dp[j][0]&＃61;1;for(int i&＃61;2;i<&＃61;26;i&＃43;&＃43;){for(__int128 j&＃61;25;j;j--){dp[j][i]&＃61;j*dp[j][i-1]&＃43;dp[j&＃43;1][i-1];if(dp[j][i]>5e19)dp[j][i]&＃61;5e19;}}int t,cas&＃61;0;scanf("%d",&t);while(t--){int n;__int128 k&＃61;0;scanf("%d%s",&n,s);int len&＃61;strlen(s);for(int i&＃61;0;i}