結果

問題 No.271 next_permutation (2)
コンテスト
ユーザー Zhang Letao
提出日時 2025-05-24 09:45:24
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 17 ms / 2,000 ms
コード長 2,453 bytes
コンパイル時間 2,203 ms
コンパイル使用メモリ 199,996 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-24 09:45:27
合計ジャッジ時間 3,343 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:45:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   45 |         scanf("%lld%lld", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
main.cpp:51:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   51 |                 scanf("%lld", &a[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 100100;
const ll mod = 1000000007;

ll n, m, a[maxn], f[maxn];
lll fac[maxn];

namespace BIT {
	int c[maxn];
	
	inline void update(int x, int d) {
		for (int i = x; i <= n; i += (i & (-i))) {
			c[i] += d;
		}
	}
	
	inline int query(int x) {
		int res = 0;
		for (int i = x; i; i -= (i & (-i))) {
			res += c[i];
		}
		return res;
	}
	
	inline int query(int l, int r) {
		return query(r) - query(l - 1);
	}
}

void solve() {
	scanf("%lld%lld", &n, &m);
	if (n == 1 || !m) {
		puts("0");
		return;
	}
	for (int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	fac[0] = 1;
	for (int i = 1;; ++i) {
		fac[i] = fac[i - 1] * i;
		if (fac[i] > 1e19) {
			break;
		}
	}
	for (int i = 1; i <= n; ++i) {
		BIT::update(a[i], 1);
		f[i] = f[i - 1] + BIT::query(a[i] + 1, n);
	}
	ll ans = f[n] % mod;
	BIT::update(a[n], -1);
	--m;
	while (m) {
		int p = n - 1;
		while (p && a[p] > a[p + 1]) {
			BIT::update(a[p--], -1);
		}
		if (!p) {
			if (fac[n] && m >= fac[n]) {
				lll t = fac[n] * n * (n - 1) / 4;
				ans = (ans + t % mod * ((m / fac[n]) % mod)) % mod;
				m %= fac[n];
			}
			if (!m) {
				break;
			}
			for (int i = 1; i <= n; ++i) {
				a[i] = i;
				if (i < n) {
					BIT::update(a[i], 1);
				}
				f[i] = 0;
			}
			--m;
			continue;
		}
		int q = n;
		while (a[p] > a[q]) {
			--q;
		}
		BIT::update(a[p], -1);
		swap(a[p], a[q]);
		BIT::update(a[p], 1);
		f[p] = f[p - 1] + BIT::query(a[p] + 1, n);
		if (fac[n - p] && m >= fac[n - p]) {
			lll t = fac[n - p] * (n - p) * (n - p - 1) / 4;
			ans = (ans + t) % mod;
			ll s = f[p] % mod;
			for (int i = p + 1; i <= n; ++i) {
				s = (s + BIT::query(a[i] + 1, n)) % mod;
			}
			for (int i = p + 1; i < n; ++i) {
				BIT::update(a[i], 1);
			}
			ans = (ans + fac[n - p] % mod * s) % mod;
			m -= fac[n - p];
		} else {
			reverse(a + p + 1, a + n + 1);
			--m;
			for (int i = p + 1; i <= n; ++i) {
				f[i] = f[i - 1] + BIT::query(a[i] + 1, n);
				if (i < n) {
					BIT::update(a[i], 1);
				}
			}
			ans = (ans + f[n]) % mod;
		}
	}
	printf("%lld\n", ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}
0