题解：P11748 「TPOI-1B」ASPAP

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

\sum_{i=1}^n \sum_{j=1}^i p_j=\sum_{i=1}^n (n-i+1)\cdot p_i

即每个

p_i

的系数为

n-i+1

。

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

系数分布：位置 $i$ 的系数为 $(n-i+1)$ ，前面的系数更大。
字典序特性：大数尽量靠前能最大化总和。
规模缩减： $n$ 很大时，只有最后 $20$ 位才会变化（题目范围给的是 $10^{18}$ ,所以只有 $20$ 个可能会有 $p_i\ne i$ ）。

参考代码

CPP

#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

。

题解：P11748 「TPOI-1B」ASPAP

文章操作

参考代码

相关推荐

评论

题解：P11748 「TPOI-1B」ASPAP