P12369题解

· · 题解

思路

价值？就是逆序对的个数。

对于 n 个数，一定有 n! 个排列，而对于每一个排列，一定有 \dfrac{n(n+1)}{2} 个满足条件的 (i,j) 二元组，而对于所有的二元组，一定有一半是逆序对。

所以对于 n 个数的所有排列中的逆序对的个数 f(n)，满足 f(n) = n! \times \frac{n(n+1)}{2} \times \frac{1}{2}，即：

f(n) = \dfrac{n! \times n(n+1)}{4}

solution

#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;
}

注意

随时取模好习惯。