复杂度O(\(n^2\))的会tle（看数据就知道了）（虽然某题解说可以，不知道是不是后期加强了数据
然而我还是写了O(\(n^2\))的
#includetypedef long long LL;LL f[1000010];const LL mod = 998244353;int a[1000010], b[1000010];int main() { f[0] = 1; for(int i = 1; i < 1000005; i++) f[i] = f[i-1] * i % mod; int n; while(~scanf("%d", &n)) { for(int i = 0; i < n; i++) { scanf("%d", &a[i]); b[a[i]] = 0; } LL ans = 1, cnt; for(int i = 0; i < n; i++) { cnt = 0; for(int j = 1; j < a[i]; j++) { if(b[j] == 0) cnt++; } b[a[i]] = 1; ans = ans % mod + cnt * f[n - i - 1]; } printf("%lld\n", ans % mod); } return 0;}
下面这个是树状数组实现的，复杂度O(nlogn) (能过)
#includetypedef long long LL;LL f[1000010];const LL mod = 998244353;int a[1000010], n, bit[1000010];void add(int i, int x) { while(i <= n) { bit[i] += x; i += i & (-i); }}int query(int i) { int res = 0; while(i > 0) { res += bit[i]; i -= i & (-i); } return res;}int main() { f[0] = 1; for(int i = 1; i < 1000005; i++) f[i] = f[i-1] * i % mod; scanf("%d", &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); add(a[i], 1); } LL ans = 1, cnt; for(int i = 1; i <= n; i++) { add(a[i], -1); cnt = query(a[i]); ans = ans % mod + cnt * f[n - i]; } printf("%lld\n", ans % mod); return 0;}
逆康拓展开O(\(n^2\))
#include#include int main() { int n, k, f[15], b[15]; f[0] = 1; for(int i = 1; i < 11; i++) f[i] = f[i-1] * i; while(~scanf("%d %d", &n, &k)) { memset(b, 0, sizeof(b)); k--; for(int i = n - 1; i >= 0; i--) { int ans = k / f[i], cnt = 0; for(int j = 1; j <= n; j++) { if(cnt == ans && b[j] == 0) { b[j] = 1; printf("%d ", j); break; } if(b[j] == 0) cnt++; } k = k % f[i]; } printf("\n"); } return 0;}
复杂度更低的我还不会 呜呜我好菜