結果

問題 No.1193 Penguin Sequence
ユーザー e869120e869120
提出日時 2021-03-05 19:16:14
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 650 ms / 2,000 ms
コード長 2,726 bytes
コンパイル時間 1,282 ms
コンパイル使用メモリ 96,220 KB
実行使用メモリ 17,540 KB
最終ジャッジ日時 2024-04-16 07:13:10
合計ジャッジ時間 28,624 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 613 ms
17,404 KB
testcase_01 AC 647 ms
17,516 KB
testcase_02 AC 648 ms
17,384 KB
testcase_03 AC 646 ms
17,512 KB
testcase_04 AC 648 ms
17,384 KB
testcase_05 AC 648 ms
17,496 KB
testcase_06 AC 647 ms
17,380 KB
testcase_07 AC 648 ms
17,388 KB
testcase_08 AC 650 ms
17,384 KB
testcase_09 AC 645 ms
17,384 KB
testcase_10 AC 648 ms
17,516 KB
testcase_11 AC 577 ms
15,932 KB
testcase_12 AC 579 ms
15,824 KB
testcase_13 AC 625 ms
17,296 KB
testcase_14 AC 617 ms
16,952 KB
testcase_15 AC 637 ms
17,160 KB
testcase_16 AC 613 ms
17,512 KB
testcase_17 AC 493 ms
14,144 KB
testcase_18 AC 505 ms
14,284 KB
testcase_19 AC 645 ms
17,360 KB
testcase_20 AC 612 ms
16,912 KB
testcase_21 AC 586 ms
15,908 KB
testcase_22 AC 507 ms
15,036 KB
testcase_23 AC 570 ms
16,128 KB
testcase_24 AC 561 ms
15,512 KB
testcase_25 AC 523 ms
14,420 KB
testcase_26 AC 500 ms
15,420 KB
testcase_27 AC 621 ms
17,012 KB
testcase_28 AC 579 ms
15,844 KB
testcase_29 AC 625 ms
17,160 KB
testcase_30 AC 537 ms
15,048 KB
testcase_31 AC 530 ms
14,704 KB
testcase_32 AC 595 ms
17,540 KB
testcase_33 AC 564 ms
15,368 KB
testcase_34 AC 550 ms
16,180 KB
testcase_35 AC 566 ms
15,636 KB
testcase_36 AC 548 ms
16,140 KB
testcase_37 AC 620 ms
16,984 KB
testcase_38 AC 496 ms
14,532 KB
testcase_39 AC 493 ms
14,952 KB
testcase_40 AC 492 ms
14,600 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

class BIT {
public:
	int size_ = 1;
	vector<int> bit;

	void init(int sz) {
		size_ = sz + 2;
		bit.resize(size_ + 2, 0);
	}
	void add(int pos, int x) {
		pos += 1;
		while (pos <= size_) {
			bit[pos] += x;
			pos += (pos & -pos);
		}
	}
	int sum(int pos) {
		pos += 1; int s = 0;
		while (pos >= 1) {
			s += bit[pos];
			pos -= (pos & -pos);
		}
		return s;
	}
};

long long modpow(long long a, long long b, long long m) {
	long long p = 1, q = a;
	for (int i = 0; i < 63; i++) {
		if ((b / (1LL << i)) % 2LL == 1) { p *= q; p %= m; }
		q *= q; q %= m;
	}
	return p;
}

long long Div(long long a, long long b, long long m) {
	return (a * modpow(b, m - 2, m)) % m;
}

long long mod = 998244353;
long long N;
long long A[1 << 18], cnt[1 << 18];
vector<long long> X;

long long fact[1 << 19];
long long factinv[1 << 19];

void init() {
	fact[0] = 1;
	for (int i = 1; i <= 300000; i++) fact[i] = (1LL * i * fact[i - 1]) % mod;
	for (int i = 0; i <= 300000; i++) factinv[i] = Div(1, fact[i], mod);
}

long long ncr(long long n, long long r) {
	if (r < 0 || n < r) return 0;
	return (fact[n] * factinv[r] % mod) * factinv[n - r] % mod;
}

int main() {
	// Step #1. 入力
	cin >> N; init();
	for (int i = 1; i <= N; i++) cin >> A[i];

	// Step #2. 座標圧縮
	for (int i = 1; i <= N; i++) X.push_back(A[i]);
	sort(X.begin(), X.end());
	X.erase(unique(X.begin(), X.end()), X.end());
	for (int i = 1; i <= N; i++) A[i] = lower_bound(X.begin(), X.end(), A[i]) - X.begin();

	// Step #3. 転倒数を求める
	long long ret1 = 0;
	BIT Z; Z.init(N + 2);
	for (int i = 1; i <= N; i++) {
		ret1 += Z.sum(N + 2) - Z.sum(A[i]);
		Z.add(A[i], 1);
	}
	ret1 %= mod;

	// Step #4. 同じペアの数を求める
	long long ret2 = 0;
	for (int i = 1; i <= N; i++) cnt[A[i]] += 1;
	for (int i = 0; i <= N; i++) ret2 += cnt[i] * cnt[i];
	ret2 %= mod;

	// Step #5. 内側・外側のペア数を求める
	long long r1 = 0, r2 = 0;
	for (int i = 1; i <= N; i++) {
		r1 += 1LL * i * (i - 1LL) / 2LL;
		r1 %= mod;
	}
	for (int i = 1; i <= N; i++) {
		long long c1 = 1LL * i * (i - 1LL) / 2LL;
		long long c2 = i;
		r2 += c1 * c2;
		r2 %= mod;
	}

	// Step #6. 答えを求める
	long long s1 = Div(ret1 % mod, (N * (N - 1) / 2LL) % mod, mod);
	long long s2 = Div((N * N - ret2) % mod, (2LL * N * N) % mod, mod);
	long long Answer = r1 * s1 + r2 * s2; Answer %= mod;
	long long Patterns = 1;
	for (int i = 1; i <= N; i++) {
		Patterns *= ncr(N, i);
		Patterns %= mod;
	}
	cout << (Answer * Patterns) % mod << endl;
	return 0;
}
0