結果

問題 No.1193 Penguin Sequence
ユーザー e869120
提出日時 2021-03-05 19:16:14
言語 C++14
(gcc 13.3.0 + boost 1.87.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

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