未来的未来の题解

· · 题解

这道题显然是DP我们可以考虑设 f_{i,j} 表示 [1,i] 的排列中逆序对个数 \bmod \ k 为 j 时的排列个数。

那么我们不难想出一个比较简单的转移。

我们可以考虑往后更新(因为比较好打)

为什么呢，其实很简单。

我们考虑放入一个新的数，前面 i-1 个数的排列我们完全不用管。

我们插入的这个数 i 一定是最大的，那么这个数对逆序对数量的贡献就为：

这个数 i 插入到排列 [1,i-1] 中它后面有多少个数。

所以一个 i 插入到 [1,i-1] 的排列中最多可以贡献 i-1 对逆序对。

最少则 0 对，我们令 l 为插入 i 后新产生的逆序对个数。

然后就能推出 f_{i+1,(j+l)\bmod k} = f_{i+1,(j+l)\bmod k} + f_{i,j}

所以就有了一个 O(n^2k) 的做法……

#include<cstdio>
#include<iostream>
#define int long long
using namespace std;
const int N=1e5+10,K=1e3+10,mod=998244353;
int n,k,f[N][K],invjc=1;
int fpow(int x,int y){
    int sum=1;
    for(;y;y>>=1ll){
        if(y&1ll)sum=(sum*x)%mod;
        x=(x*x)%mod;
    }
    return sum;
}
int inv(int x){return fpow(x,mod-2);}
signed main(){
    scanf("%lld%lld",&n,&k);
    f[1][0]=1;
    for(int i=2;i<=n;++i)invjc=(invjc*i)%mod;
    invjc=inv(invjc);
    for(int i=1;i<n;++i){
        for(int j=0;j<k;++j){
            for(int l=0;l<=i;++l){
                f[i+1][(j+l)%k]=(f[i+1][(j+l)%k]+f[i][j])%mod;
            }
        }
    }
    for(int i=0;i<k;++i)printf("%lld ",(f[n][i]*invjc)%mod);
    puts("");
    return (0^0);
}

稳稳地T飞了

所以我们可以开始考虑优化。

空间

对于这种只由前一层更新过来的我们通常会使用滚动数组。

这样空间就不会炸了。(好像不开没炸？？？)

时间

我们尝试提高代码复杂度将DP的转移从从前往后更新改为从由前面转移。

会麻烦一些，我们先定义下限 d=(j-i+1)\bmod k

那么我们会推出以下转移方程

当 d \le j 时 只要 d \le x \le j 时 f_{i-1,x} 是可以更新到 f_{i,j} 的。

因为如上文所述，每次插入的 i 可以至多产生 i-1 个逆序对。

最少则为 0 个。

所以在这个下限 d 到上限 j 这个范围内都是可以更新过来的。

为什要考虑 d 的大小呢？

因为 这个 d 是 \bmod \ k 意义下的，所以原始可能为负，

那么 d 就会大于 j 。

此时当 d \le x < n 时 f_{i-1,x} 也是对 f_{i,j} 有贡献的。

但是还有 0 \le x \le j 的这一部分，我们也要算上。

综上所述，我们要两种讨论去转移。

然后就有了DP由前面转移的版本。

#include<cstdio>
#include<iostream>
#define int long long
using namespace std;
const int K=1e3+10,mod=998244353;
int n,k,f[2][K],invjc=1;
int fpow(int x,int y){
    int sum=1;
    for(;y;y>>=1ll){
        if(y&1ll)sum=(sum*x)%mod;
        x=(x*x)%mod;
    }
    return sum;
}
int inv(int x){return fpow(x,mod-2);}
signed main(){
    scanf("%lld%lld",&n,&k);
    f[1][0]=1;
    for(int i=2;i<=n;++i)invjc=(invjc*i)%mod;
    invjc=inv(invjc);
    for(int i=2;i<=n;++i){
        int u=(i&1),v=(u^1);
        for(int j=0;j<k;++j){
            int d=((j-i+1)%k+k)%k;
            if(d<=j)for(int l=d;l<=j;++l)f[u][j]=(f[u][j]+f[v][l])%mod;
            else{
                for(int l=d;l<k;++l)f[u][j]=(f[u][j]+f[v][l])%mod;
                for(int l=0;l<=j;++l)f[u][j]=(f[u][j]+f[v][l])%mod;
            }
        }
        for(int j=0;j<k;++j)f[v][j]=0;
    }
    for(int i=0;i<k;++i)printf("%lld ",(f[(n&1)][i]*invjc)%mod);
    puts("");
    return (0^0);
}

居然有分！！！

其实时间复杂度还是 O(n^2k) 但是这样就可以方便我们优化了。

我们发现每次 f_{i,j} 的转移都是由连续的一段或两段的上一次的DP值转移的。

所以我们搞一个前缀和优化，每次转移就是 O(1) 的了！

但是由于取模常数很玄学ex。

这样带滚动数组的 O(nk) 做法过不了……

所以我打表发现了一个规律。

当 n \ge k 时，所有值的答案都为 1/k 所以这样 O(nk) 做法就蜕变为 O(k^2) 做法啦！！！

取模常数啥的就基本没问题了！

然后就可以欢乐AC了！

AC code

#include<cstdio>
#include<iostream>
#define int long long
using namespace std;
const int K=1e3+10,mod=998244353;
int n,k,f[2][K],g[2][K],invjc=1;
int fpow(int x,int y){
    int sum=1;
    for(;y;y>>=1ll){
        if(y&1ll)sum=(sum*x)%mod;
        x=(x*x)%mod;
    }
    return sum;
}
int inv(int x){return fpow(x,mod-2);}
signed main(){
    scanf("%lld%lld",&n,&k);
    if(n>k){
        n=inv(k);
        for(;k--;)printf("%lld ",n);
        puts("");
        return (0^0);
    }
    f[1][0]=g[1][0]=1;
    for(int i=1;i<k;++i)g[1][i]=1;
    for(int i=2;i<=n;++i)invjc=(invjc*i)%mod;
    invjc=inv(invjc);
    for(int i=2;i<=n;++i){
        int u=(i&1),v=(u^1);
        for(int j=0;j<k;++j){
            int d=((j-i+1)%k+k)%k;
            if(d<=j){
                if(d==0)f[u][j]=(g[v][j])%mod;
                else f[u][j]=((g[v][j]-g[v][d-1])%mod+mod)%mod;
            }
            else{
                f[u][j]=((g[v][k-1]-g[v][d-1])%mod+mod)%mod;
                f[u][j]=(f[u][j]+g[v][j])%mod;
            }
            if(j==0)g[u][j]=f[u][j];
            else g[u][j]=(g[u][j-1]+f[u][j])%mod;
        }
    }
    for(int i=0;i<k;++i)printf("%lld ",(f[(n&1)][i]*invjc)%mod);
    puts("");
    return (0^0);
}

小小的提示：

注意负数取模和最后乘上全排列总数的逆元。

祝A (看到这了还不点赞吗QWQ)