自动搬运

查看原文

来自洛谷，原作者为

	SpeMars 不当棕名金钩不改签名

搬运于2025-08-24 22:36:03，当前版本为作者最后更新于2022-02-09 20:51:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这道题显然是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)