企业官网建设流程全解析

P11748 「TPOI-1B」ASPAP

题目描述

你有n!n!n!个长度为nnn的排列，它们已经按照字典序排好了顺序。

请你在字典序顺序中前SSS个排列里寻找一个排列ppp，使得∑i=1n∑j=1ipj\displaystyle\sum_{i=1}^n\sum_{j=1}^{i}p_ji=1∑n​j=1∑i​pj​最大。你只需要输出这个最大值即可。

由于答案可能很大，请输出答案对998244353998244353998244353取模的结果。

输入格式

第一行，一个整数TTT。

接下来TTT行，每行两个整数n,Sn,Sn,S。

输出格式

共TTT行，每行一个整数，表示最大的∑i=1n∑j=1ipj\displaystyle\sum_{i=1}^n\sum_{j=1}^{i}p_ji=1∑n​j=1∑i​pj​，对998244353998244353998244353取模。

输入输出样例 #1

输入 #1

1 4 5

输出 #1

23

说明/提示

【样例 #1 解释】

长度为444的排列的前五个分别为：

1,2,3,4→1+(1+2)+(1+2+3)+(1+2+3+4)=201,2,3,4 \to 1+(1+2)+(1+2+3)+(1+2+3+4)=201,2,3,4→1+(1+2)+(1+2+3)+(1+2+3+4)=20

1,2,4,3→1+(1+2)+(1+2+4)+(1+2+4+3)=211,2,4,3 \to 1+(1+2)+(1+2+4)+(1+2+4+3)=211,2,4,3→1+(1+2)+(1+2+4)+(1+2+4+3)=21

1,3,2,4→1+(1+3)+(1+3+2)+(1+3+2+4)=211,3,2,4 \to 1+(1+3)+(1+3+2)+(1+3+2+4)=211,3,2,4→1+(1+3)+(1+3+2)+(1+3+2+4)=21

1,3,4,2→1+(1+3)+(1+3+4)+(1+3+4+2)=231,3,4,2 \to 1+(1+3)+(1+3+4)+(1+3+4+2)=231,3,4,2→1+(1+3)+(1+3+4)+(1+3+4+2)=23

1,4,2,3→1+(1+4)+(1+4+2)+(1+4+2+3)=231,4,2,3 \to 1+(1+4)+(1+4+2)+(1+4+2+3)=231,4,2,3→1+(1+4)+(1+4+2)+(1+4+2+3)=23

最大值为232323。

【数据范围】

对于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++实现

#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=25,mod=998244353,_2=499122177,_6=166374059;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));ans=0;}intF(intx){returnx*(x+1)%mod*_2%mod;}//1+2+3+···+n=F(n)intG(intx){returnx*(x+1)%mod*(2*x%mod+1)%mod*_6%mod;}//1^2+2^2+3^2+···+n^2=G(n)signedmain(){fac[0]=1;for(inti=1;i<=20;i++)fac[i]=fac[i-1]*i;scanf("%lld",&T);while(T--){clean();scanf("%lld%lld",&n,&S);intsum=0;intlen=min(n,20ll);for(inti=n-len+1;i<=n;i++)rak[i-(n-len+1)+1]=i-(n-len+1)+1,rhk[i-(n-len+1)+1]=i;for(inti=n-len+1,cnt=len;i<=n;i++){inttot,last;for(intj=len;j>=1;j--)if(!vis[j]&&S>fac[n-i]*(rak[j]-1)){S-=fac[n-i]*(rak[j]-1);vis[j]=1;tot=rhk[rak[j]];last=rhk[rak[j]-1];break;}if(last!=0){intSum=sum+last*(n-i+1);for(intj=i+1,k=cnt;j<=n&&k>=1;j++,k--){if(rhk[k]==last)k--;Sum+=rhk[k]*(n-j+1);}ans=max(Sum,ans);}//这里的if语句就是处理次大的情况。cnt=0;for(intj=1;j<=len;j++){if(vis[j]){rak[j]=0;continue;}elsecnt++,rak[j]=cnt,rhk[cnt]=(n-len+1)+j-1;}sum+=tot*(n-i+1);}ans=max(ans,sum);//所有数放完，再统计。ans%=mod;if(n>20){intm=n-20;ans+=((n+1)%mod*F(m)%mod-G(m)+mod)%mod,ans%=mod;//前面的贡献。}printf("%lld\n",ans);}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容