题解：P11748 「TPOI-1B」ASPAP

zaz_dreamtraveler · 2025-11-26 19:28:02 · 题解

先看题目中的前缀和公式：

即每个 p_i 的系数为 n-i+1。

这道题目有三个要注意的点：

• 系数分布：位置 i的系数为 (n-i+1) ，前面的系数更大。

• 字典序特性：大数尽量靠前能最大化总和。

• 规模缩减：n 很大时，只有最后 20 位才会变化 （ 题目范围给的是 10^{18} ,所以只有 20 个可能会有 p_i\ne i ）。

参考代码

#include<bits/stdc++.h>
using namespace std;
const int MOD=998244353;
long long f(long long x){
    return x*(x+1)%MOD*(x+2)%MOD*166374059%MOD;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        long long n,s;
        cin>>n>>s;
        long long p=1,fac=1;
        for(;p<=n;p++){
            fac*=p;
            if(fac*(p+1)>s) break;
        }
        p++;
        long long ans=f(n-p),mx=0;
        int v[21]={0},a[21]={0};
        for(int i=1;i<p;i++){
            long long t=(s+fac-1)/fac;
            int sec=0,cnt=0;
            for(int j=1;j<=p;j++){
                if(!v[j]&&++cnt==t-1){
                    sec=j;
                    break;
                }
            }
            if(sec){
                int v2[21]={0};
                for(int j=1;j<=p;j++) v2[j]=v[j];
                v2[sec]=1;
                a[i]=sec+n-p;
                int idx=i;
                long long tmp=ans,sum=(n-p)*(n-p+1)/2%MOD;
                for(int j=p;j>=1;j--) if(!v2[j]) a[++idx]=j+n-p;
                for(int j=1;j<=p;j++){
                    ans=(ans+sum+a[j])%MOD;
                    sum=(sum+a[j])%MOD;
                }
                mx=max(mx,ans);
                ans=tmp;
                for(int j=i;j<=p;j++) a[j]=0;
            }
            cnt=0;
            for(int j=1;j<=p;j++){
                if(!v[j]&&++cnt==t){
                    a[i]=j+n-p;
                    v[j]=1;
                    break;
                }
            }
            if(fac) s%=fac;
            if(!s) s=fac;
            fac/=(p-i);
        }
        for(int i=1;i<=p;i++){
            if(!v[i]){
                a[p]=i+n-p;
                break;
            }
        }
        long long sum=(n-p)*(n-p+1)/2%MOD;
        for(int i=1;i<=p;i++){
            ans=(ans+sum+a[i])%MOD;
            sum=(sum+a[i])%MOD;
        }
        mx=max(mx,ans);
        cout<<mx<<endl;
    }
    return 0;
}

代码还是稍慢的，达到了 800ms 。