拓冰网站定制 
P11748 「TPOI-1B」ASPAP题目描述你有n!n!n!个长度为nnn的排列它们已经按照字典序排好了顺序。请你在字典序顺序中前SSS个排列里寻找一个排列ppp使得∑i1n∑j1ipj\displaystyle\sum_{i1}^n\sum_{j1}^{i}p_ji1∑nj1∑ipj最大。你只需要输出这个最大值即可。由于答案可能很大请输出答案对998244353998244353998244353取模的结果。输入格式第一行一个整数TTT。接下来TTT行每行两个整数n,Sn,Sn,S。输出格式共TTT行每行一个整数表示最大的∑i1n∑j1ipj\displaystyle\sum_{i1}^n\sum_{j1}^{i}p_ji1∑nj1∑ipj对998244353998244353998244353取模。输入输出样例 #1输入 #11 4 5输出 #123说明/提示【样例 #1 解释】长度为444的排列的前五个分别为1,2,3,4→1(12)(123)(1234)201,2,3,4 \to 1(12)(123)(1234)201,2,3,4→1(12)(123)(1234)201,2,4,3→1(12)(124)(1243)211,2,4,3 \to 1(12)(124)(1243)211,2,4,3→1(12)(124)(1243)211,3,2,4→1(13)(132)(1324)211,3,2,4 \to 1(13)(132)(1324)211,3,2,4→1(13)(132)(1324)211,3,4,2→1(13)(134)(1342)231,3,4,2 \to 1(13)(134)(1342)231,3,4,2→1(13)(134)(1342)231,4,2,3→1(14)(142)(1423)231,4,2,3 \to 1(14)(142)(1423)231,4,2,3→1(14)(142)(1423)23最大值为232323。【数据范围】Subtask\text{Subtask}Subtask分值特殊性质111101010n≤8n\le8n≤8222101010T≤20,n≤16T\le20,n\le16T≤20,n≤16333252525T≤104T\le10^4T≤104444555Sn!Sn!Sn!555505050无特殊性质对于100%100\%100%的数据1≤T≤105,1≤n≤109,1≤S≤min(n!,1018)1 \le T \le 10^5, 1 \le n \le 10^9, 1 \le S \le \min(n!,10^{18})1≤T≤105,1≤n≤109,1≤S≤min(n!,1018)。C实现#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN25,mod998244353,_2499122177,_6166374059;intT,n,S,ans,fac[N],rak[N],rhk[N];boolvis[N];voidclean(){memset(rak,0,sizeof(rak));memset(rhk,0,sizeof(rhk));memset(vis,0,sizeof(vis));ans0;}intF(intx){returnx*(x1)%mod*_2%mod;}//123···nF(n)intG(intx){returnx*(x1)%mod*(2*x%mod1)%mod*_6%mod;}//1^22^23^2···n^2G(n)signedmain(){fac[0]1;for(inti1;i20;i)fac[i]fac[i-1]*i;scanf(%lld,T);while(T--){clean();scanf(%lld%lld,n,S);intsum0;intlenmin(n,20ll);for(intin-len1;in;i)rak[i-(n-len1)1]i-(n-len1)1,rhk[i-(n-len1)1]i;for(intin-len1,cntlen;in;i){inttot,last;for(intjlen;j1;j--)if(!vis[j]Sfac[n-i]*(rak[j]-1)){S-fac[n-i]*(rak[j]-1);vis[j]1;totrhk[rak[j]];lastrhk[rak[j]-1];break;}if(last!0){intSumsumlast*(n-i1);for(intji1,kcnt;jnk1;j,k--){if(rhk[k]last)k--;Sumrhk[k]*(n-j1);}ansmax(Sum,ans);}//这里的if语句就是处理次大的情况。cnt0;for(intj1;jlen;j){if(vis[j]){rak[j]0;continue;}elsecnt,rak[j]cnt,rhk[cnt](n-len1)j-1;}sumtot*(n-i1);}ansmax(ans,sum);//所有数放完再统计。ans%mod;if(n20){intmn-20;ans((n1)%mod*F(m)%mod-G(m)mod)%mod,ans%mod;//前面的贡献。}printf(%lld\n,ans);}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容 打卡信奥刷题（3612）用C++实现信奥题 P11748 「TPOI-1B」ASPAP
P11748 「TPOI-1B」ASPAP题目描述你有n!n!n!个长度为nnn的排列它们已经按照字典序排好了顺序。请你在字典序顺序中前SSS个排列里寻找一个排列ppp使得∑i1n∑j1ipj\displaystyle\sum_{i1}^n\sum_{j1}^{i}p_ji1∑nj1∑ipj最大。你只需要输出这个最大值即可。由于答案可能很大请输出答案对998244353998244353998244353取模的结果。输入格式第一行一个整数TTT。接下来TTT行每行两个整数n,Sn,Sn,S。输出格式共TTT行每行一个整数表示最大的∑i1n∑j1ipj\displaystyle\sum_{i1}^n\sum_{j1}^{i}p_ji1∑nj1∑ipj对998244353998244353998244353取模。输入输出样例 #1输入 #11 4 5输出 #123说明/提示【样例 #1 解释】长度为444的排列的前五个分别为1,2,3,4→1(12)(123)(1234)201,2,3,4 \to 1(12)(123)(1234)201,2,3,4→1(12)(123)(1234)201,2,4,3→1(12)(124)(1243)211,2,4,3 \to 1(12)(124)(1243)211,2,4,3→1(12)(124)(1243)211,3,2,4→1(13)(132)(1324)211,3,2,4 \to 1(13)(132)(1324)211,3,2,4→1(13)(132)(1324)211,3,4,2→1(13)(134)(1342)231,3,4,2 \to 1(13)(134)(1342)231,3,4,2→1(13)(134)(1342)231,4,2,3→1(14)(142)(1423)231,4,2,3 \to 1(14)(142)(1423)231,4,2,3→1(14)(142)(1423)23最大值为232323。【数据范围】Subtask\text{Subtask}Subtask分值特殊性质111101010n≤8n\le8n≤8222101010T≤20,n≤16T\le20,n\le16T≤20,n≤16333252525T≤104T\le10^4T≤104444555Sn!Sn!Sn!555505050无特殊性质对于100%100\%100%的数据1≤T≤105,1≤n≤109,1≤S≤min(n!,1018)1 \le T \le 10^5, 1 \le n \le 10^9, 1 \le S \le \min(n!,10^{18})1≤T≤105,1≤n≤109,1≤S≤min(n!,1018)。C实现#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN25,mod998244353,_2499122177,_6166374059;intT,n,S,ans,fac[N],rak[N],rhk[N];boolvis[N];voidclean(){memset(rak,0,sizeof(rak));memset(rhk,0,sizeof(rhk));memset(vis,0,sizeof(vis));ans0;}intF(intx){returnx*(x1)%mod*_2%mod;}//123···nF(n)intG(intx){returnx*(x1)%mod*(2*x%mod1)%mod*_6%mod;}//1^22^23^2···n^2G(n)signedmain(){fac[0]1;for(inti1;i20;i)fac[i]fac[i-1]*i;scanf(%lld,T);while(T--){clean();scanf(%lld%lld,n,S);intsum0;intlenmin(n,20ll);for(intin-len1;in;i)rak[i-(n-len1)1]i-(n-len1)1,rhk[i-(n-len1)1]i;for(intin-len1,cntlen;in;i){inttot,last;for(intjlen;j1;j--)if(!vis[j]Sfac[n-i]*(rak[j]-1)){S-fac[n-i]*(rak[j]-1);vis[j]1;totrhk[rak[j]];lastrhk[rak[j]-1];break;}if(last!0){intSumsumlast*(n-i1);for(intji1,kcnt;jnk1;j,k--){if(rhk[k]last)k--;Sumrhk[k]*(n-j1);}ansmax(Sum,ans);}//这里的if语句就是处理次大的情况。cnt0;for(intj1;jlen;j){if(vis[j]){rak[j]0;continue;}elsecnt,rak[j]cnt,rhk[cnt](n-len1)j-1;}sumtot*(n-i1);}ansmax(ans,sum);//所有数放完再统计。ans%mod;if(n20){intmn-20;ans((n1)%mod*F(m)%mod-G(m)mod)%mod,ans%mod;//前面的贡献。}printf(%lld\n,ans);}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容