题解：P11748 「TPOI-1B」ASPAP

· · 题解

这题竟然才绿啊，亏我调了3个小时。

其实这个题只需要有两个重要的点，其他都是比较简单的对吧：

  1. 怎么找到贪心策略。

这个其实也不难，手模一下阳历可以发现，第 S 个答案并不是最优解！这个随便可以举出反例。但是，可以细致的发现，一般将较大数放在较前面是很优的，但可能也会顾此失彼！比如阳历中出现的两种答案相等的情况，如果再在答案中加一个 5 那样的话易证贪心失效。但是也考虑这种贪心也是有合理性的，因为假如没有 S 的限制的话可以随意从大到小排序，直接给出答案。

思考为什么贪心不成立呢？因为 S 的限制。

我们可以分情况讨论，肯定有前一部分排列的最大答案中出现从大到小排序的部分，我们称该排列及之前的部分为不受 S 限制的部分，而后面的部分因为没有办法达到从大到小排列，所以称为受 S 限制的部分。没有 S 限制的部分直接将可排序的部分（怎么定一会儿说）排序得到答案。之后的部分，又该怎么处理？相当于我们又限制了一位（因为当我们考虑时是一位一位考虑的）。直接把得到答案的重任交给下一位，同时减掉本位到达这一位的方案数，因此可以采用递归求解，下一位时再考虑如上操作，直到最后一位。也就是说，要么顶着限制，继续前进，将位数卡满，要么放弃限制，但获得可以直接排序的机会。

诶？这不数位dp嘛（类似）。

嗯，如果只想到这里的话，那么，恭喜你，这是第一步，但是只想到这，还是远远不够的。

理想很丰满，现实很骨感，你看看那个 n 那是给过的？

  1. 优化，优化，还是优化！

我们这个贪心策略，确实是对的，但是复杂度差到家了。有没有更好的方法呢？

观察到 S 的数据范围，还是很小的（小？）。考虑 20!>10^{18} 所以能改变的位不超 20 个！这是个非常重要的性质。所以我们考虑时直接从后二十位考虑就行了。

这个优化已经很好了，但还远远不够 1e9 的零头。毕竟枚举一遍需要很高的时间复杂度！太不友好了！将序列拆成前后两个，前面的肯定是顺序，而后面的是自己贪的。前面那些数，扫一遍都不行。前面不变的数怎么办？难道还能不扫？还真是。

一个顺序序列（假设就是从小到大的），考虑贡献，也无非是 \displaystyle\sum_{i=1}^n\sum_{j=1}^{i}j，由等差序列求和公式可知 \displaystyle\sum_{i=1}^n\sum_{j=1}^{i}j=\displaystyle\sum_{i=1}^n \frac{i\times (i+1)}{2} 好像也不明显，再该一下 \displaystyle\sum_{i=1}^n i\times (i+1)=\displaystyle\sum_{i=1}^n i^2+\displaystyle\sum_{i=1}^n i 这就要不得不提一个公式了 \displaystyle\sum_{i=1}^n i^2=\frac{(2n+1)(n+1)n}{6} 了，带入原式 \displaystyle\sum_{i=1}^n\sum_{j=1}^{i}j=\frac{(2n+1)(n+1)n}{12}+\frac{(n+1)n}{4} 这个可以在 O(1) 的时间内实现！虽然实际情况少了一块（后面），但是后面的贡献可以自己计算减掉（按照顺序排列的后面一部分），再加上贪心的答案，完美！

再说说上文说的怎么分前后两个序列呢？先通过遍历，找到 S 恰好小于 a! 的数字，此时，后 a 位就是想要的答案了。至于递归到下一层时，减掉的是从小到大可以所有可以填的数字减掉 a-1 的全排列就行了。（这个实现真的恶心。）

好了，是时候上代码了。

#include<bits/stdc++.h>
using namespace std;//（这里为了省事直接开 __int128）
#define int __int128
int t,mp[25],vis[25];
const int mod=998244353;
void write(int x){
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int dfs(int k,int x,int n,bool f,int S,int sum){
    if(x==n){
        //write(f);putchar(' ');write(v[0]);putchar(' ');write(v.size());putchar(' ');write(sum+v[0]);puts("");
        for(int i=0;i<=n-k;i++){
            if(!vis[i])return sum+i+k;
        }
    }
    if(!f){
        int ans=0,tot=0;
        //for(int i=0;i<len;i++)ans+=(i+1)*v[i];
        for(int i=0;i<=n-k;i++){
            if(!vis[i]){
                ans+=(++tot)*(k+i);
            }
        }
        //write(x);putchar(' ');write(S);putchar(' ');write(ans);putchar(' ');write(sum);putchar(' ');
    //puts("");
        return sum+ans;
    }
    int ans=0;
    for(int j=0;j<=n-k;j++){
        if(vis[j])continue;
        int i=j+k;
        //for(int j:v)if(i!=j)q.push_back(j);
        vis[j]=1;
        ans=max(ans,dfs(k,x+1,n,(S-mp[n-x]<=0),S,sum+(n-x+1)*i));
        vis[j]=0;
        S-=mp[n-x];
        if(S<=0)break;
    }
    return ans;
}
inline int read(){
    int x=0;char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c<='9'&&c>='0'){
        x=(x<<3)+(x<<1)+c-48;
        c=getchar();
    }
    return x;
}
void solve(){
    int n=read(),S=read(),f=1;
    //write(S);puts("");
    for(int i=n;i>=1;i--){
        int j=n-i+1;
        if(S<mp[j]){
            f=i;break;
        }
        //write(mp[j]);
    }
    //write(f);puts("");
    int ans=0;
    for(int i=f;i<=n;i++){
        //vector<int>v;
        //for(int j=f;j<=n;j++)if(i!=j)v.push_back(j);
        vis[i-f]=1;
        ans=max(ans,dfs(f,f+1,n,(S-mp[n-f]<=0),S,(n-f+1)*i));
        vis[i-f]=0;
        S-=mp[n-f];
        if(S<=0)break;
    }
    int tp1=(n*(n+1)*(2*n+1)/6+n*(n+1)/2)/2;
    //write(tp1);puts("");
    int tp2=0;
    for(int i=f;i<=n;i++){
        tp2+=i*(n-i+1);
    }
    int sum=(ans+tp1-tp2)%mod;
    //write(ans);puts("");
    write(sum);
    puts("");
    return ;
}
signed main(){
    t=read();
    mp[1]=1;
    for(int i=2;i<=21;i++){
        mp[i]=mp[i-1]*i;
    }
    while(t--){
        solve();
    }
}