客挑战赛46 C题

牛客挑战赛46 C题
题解：f[i][k][j]表示前i个k个逆序对且最大数的位置在j处的数目,第一维需要用滚动数组优化，但是求f[i][k][j]的时候会发现需要对前i-1长度排列的最大数的位置进行枚举，这一层可以用以个sum[i][k][j]优化，sum[i][k][j]表示长度为i的排列最大数的位置从1到j并且超级逆序对为k的个数总和

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=2e6+10;
const LL mod=998244353;
LL n,K;
LL f[3][505][505];
LL sum[3][505][505];
LL ksm(LL x,LL N)
{
    LL ans=1;
    LL tmp=x%mod;
    while(N){
        if(N&1){
            ans*=tmp;
            ans%=mod;
        }
        tmp*=tmp;
        tmp%=mod;
        N/=2;
    }
    return ans;
}
int main()
{
    scanf("%lld%lld",&n,&K);
    memset(f,0,sizeof(f));
    memset(sum,0,sizeof(sum));
    f[1][0][1]=1;
    sum[1][0][1]=1;
    LL pre=2;
    for(register LL i=2;i<=n;++i){
         for(register LL k=0;k<=K;++k){
            for(register LL j=1;j<=i-1;++j){
                f[pre][k][j]=0;
                if(k-(i-j-1)>=0){
                    f[pre][k][j]=sum[pre^3][k-(i-j-1)][i-1]-sum[pre^3][k-(i-j-1)][j-1];
                    f[pre][k][j]%=mod;
                    f[pre][k][j]=(f[pre][k][j]+mod)%mod;
                }
                if(k-(i-j)>=0){
                    f[pre][k][j]+=sum[pre^3][k-(i-j)][j-1];
                    f[pre][k][j]%=mod;
                }
                sum[pre][k][j]=sum[pre][k][j-1]+f[pre][k][j];
                sum[pre][k][j]%=mod;
           }
           f[pre][k][i]=sum[pre^3][k][i-1];
           sum[pre][k][i]=sum[pre][k][i-1]+f[pre][k][i];
           sum[pre][k][i]%=mod;
        }
        pre^=3;
      }
    if(n%2){
        pre=1;
    }
    else{
        pre=2;
    }
    LL ans=0;
    for(register LL i=1;i<=n;++i){
        ans+=f[pre][K][i];
        ans%=mod;
    }
    printf("%lld\n",ksm(ans,mod-2));
    return 0;
}