题面：[HZOI]CSP-S模拟12 & 多校2025暑假集训模拟赛8 T3
大意简述：给定一个长度为 \(n\) 的序列，给定 \(k\) 与 \(mod\) 。求该序列 \(k\) 个下个排列的逆序对求和。
赛时看了一眼题，嗯。。。
如果暴力枚举每个序列的话肯定 \(TLE\) 。因为 \(k /in [1,1e18]\) ，所以直接放弃暴力，开始乱搞。（赛后事实证明乱搞跟暴力分一样高）
开始手膜样例。
自己手膜了 \(n\)
#include<bits/stdc++.h>
// #define getchar_unlocked getchar
// #define putchar_unlocked putchar
#define ent putchar_unlocked('\n')
#define con putchar_unlocked(' ')
#define int __uint128_t
#define Blue_Archive return 0
using namespace std;
const int N = 5e5 + 3;int n;
int k;
int mod;
int ans;
int top;int a[N];
int f[N];
int g[N];
int t[N];bool vis[N];inline int read()
{int x = 0,f = 1;char c = getchar_unlocked();while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar_unlocked();}while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0',c = getchar_unlocked();return x * f;
}inline void write(int x)
{if(x < 0) putchar_unlocked('-'),x = -x;if(x > 9) write(x / 10);putchar_unlocked(x % 10 + '0');
}inline void init()
{f[1] = 0;g[1] = 1;t[1] = 1;for(int i = 2;i <= n;i ++){t[i] = (t[i - 1] + i) % mod;g[i] = g[i - 1] * i;f[i] = (f[i - 1] * i % mod + g[i - 1] * t[i - 1] % mod) % mod;}
}inline int find()
{if(n == 0) return 0;int res = 0;vis[a[1]] = 1;res += (a[1] - 1) * g[n - 1] % mod;for(int i = 2;i <= n;i ++){for(int j = 1;j < a[i];j ++){if(vis[j]) continue;res += g[n - i];}vis[a[i]] = 1;}return res + 1;
}inline int solve(int skk)
{if(skk == 0) return 0;int res = 0;int op = skk / g[n];res = op * f[n] % mod;skk %= g[n];for(int i = n - 1,tim;i >= 1;i --){tim = skk / g[i];skk %= g[i];res += t[tim - 1] * g[i] + f[i] * tim;res += skk * tim;}return res;
}signed main()
{// freopen("3.in","r",stdin);// freopen("3.out","w",stdout);freopen("army.in","r",stdin);freopen("army.out","w",stdout);n = read();k = read();mod = read();init();for(int i = 1;i <= n;i ++) a[i] = read();int jk = find();ans = solve(k + jk - 1) - solve(jk - 1);write((ans % mod + mod) % mod);ent;Blue_Archive;
}