专栏文章

P12369题解

NNahia
P12369题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip4fghe
此快照首次捕获于
2025/12/03 05:59
3 个月前
此快照最后确认于
2025/12/03 05:59
3 个月前
查看原文

思路

价值？就是逆序对的个数。
对于 nn 个数，一定有 n!n! 个排列，而对于每一个排列，一定有 n(n+1)2\dfrac{n(n+1)}{2} 个满足条件的 (i,j)(i,j) 二元组，而对于所有的二元组，一定有一半是逆序对。
所以对于 nn 个数的所有排列中的逆序对的个数 f(n)f(n)，满足 f(n)=n!×n(n+1)2×12f(n) = n! \times \frac{n(n+1)}{2} \times \frac{1}{2}，即：
f(n)=n!×n(n+1)4f(n) = \dfrac{n! \times n(n+1)}{4}

solution

CPP
#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(int i = a;i<=b;i++)
using namespace std;
inline __int128 read(){__int128 x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-'){f=-1;}c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return f*x;}
inline void write(__int128 x){if(x<0){putchar('-');x=-x;}if(x>9)write(x/10);putchar(x%10+'0');}
const ll N = 1000010;
const ll mod = 998244353;
ll n,a[N],f[N]={1,1};
int main(){
	int n = read();
	a[2] = 1;
	For(i,1,N) f[i] = f[i-1]*i%mod;
	For(i,1,n){
		a[i] = (1ll*i*a[i-1]%mod+1ll*i*(i-1)/2%mod*1*f[i-1]%mod)%mod;
	}
	write(a[n]);
	return 0;
}

注意

随时取模好习惯。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...