結果

問題 No.1193 Penguin Sequence
ユーザー e869120e869120
提出日時 2021-03-05 19:16:14
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 712 ms / 2,000 ms
コード長 2,726 bytes
コンパイル時間 1,110 ms
コンパイル使用メモリ 95,452 KB
実行使用メモリ 13,512 KB
最終ジャッジ日時 2024-10-06 21:25:53
合計ジャッジ時間 28,557 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 615 ms
13,508 KB
testcase_01 AC 643 ms
13,508 KB
testcase_02 AC 645 ms
13,380 KB
testcase_03 AC 644 ms
13,384 KB
testcase_04 AC 712 ms
13,512 KB
testcase_05 AC 645 ms
13,448 KB
testcase_06 AC 642 ms
13,504 KB
testcase_07 AC 642 ms
13,384 KB
testcase_08 AC 645 ms
13,376 KB
testcase_09 AC 643 ms
13,512 KB
testcase_10 AC 642 ms
13,504 KB
testcase_11 AC 575 ms
11,164 KB
testcase_12 AC 577 ms
11,180 KB
testcase_13 AC 623 ms
12,780 KB
testcase_14 AC 612 ms
12,304 KB
testcase_15 AC 634 ms
13,028 KB
testcase_16 AC 608 ms
11,844 KB
testcase_17 AC 492 ms
8,064 KB
testcase_18 AC 507 ms
8,832 KB
testcase_19 AC 643 ms
13,488 KB
testcase_20 AC 610 ms
12,264 KB
testcase_21 AC 589 ms
11,392 KB
testcase_22 AC 507 ms
8,680 KB
testcase_23 AC 568 ms
10,972 KB
testcase_24 AC 558 ms
10,484 KB
testcase_25 AC 522 ms
9,204 KB
testcase_26 AC 501 ms
8,448 KB
testcase_27 AC 618 ms
12,496 KB
testcase_28 AC 579 ms
11,204 KB
testcase_29 AC 621 ms
12,652 KB
testcase_30 AC 537 ms
9,600 KB
testcase_31 AC 528 ms
9,388 KB
testcase_32 AC 592 ms
11,724 KB
testcase_33 AC 562 ms
10,512 KB
testcase_34 AC 548 ms
10,116 KB
testcase_35 AC 563 ms
10,520 KB
testcase_36 AC 545 ms
10,096 KB
testcase_37 AC 617 ms
12,464 KB
testcase_38 AC 494 ms
8,320 KB
testcase_39 AC 495 ms
8,192 KB
testcase_40 AC 493 ms
8,192 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