結果

問題 No.271 next_permutation (2)
ユーザー levitate921
提出日時 2025-05-24 14:05:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 8,470 bytes
コンパイル時間 2,553 ms
コンパイル使用メモリ 198,068 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-24 14:05:30
合計ジャッジ時間 3,802 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

//yukicoder271
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
namespace FastIO {
#if __cplusplus > 201700
#define INLINE_V inline
#else
#define INLINE_V
#endif
#if (defined(LOCAL) || defined(_WIN32)) && !defined(DISABLE_MMAP)
#define DISABLE_MMAP
#endif
#ifndef DISABLE_MMAP
#include <sys/mman.h>
#endif
INLINE_V constexpr int _READ_SIZE = 1 << 18; INLINE_V static char _read_buffer[_READ_SIZE], *_read_ptr = nullptr, *_read_ptr_end = nullptr;
inline char gc() { if (__builtin_expect(_read_ptr == _read_ptr_end, false)) { _read_ptr = _read_buffer; _read_ptr_end = _read_buffer + fread(_read_buffer, 1, _READ_SIZE, stdin); if (__builtin_expect(_read_ptr == _read_ptr_end, false)) return EOF;} return *_read_ptr++; }
INLINE_V constexpr int _WRITE_SIZE = 1 << 18; INLINE_V static char _write_buffer[_WRITE_SIZE], *_write_ptr = _write_buffer; inline void pc(char c) { *_write_ptr++ = c; if (__builtin_expect(_write_buffer + _WRITE_SIZE == _write_ptr, false)) { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); _write_ptr = _write_buffer; } }
INLINE_V struct _auto_flush { ~_auto_flush() { fwrite(_write_buffer, 1, _write_ptr - _write_buffer, stdout); } } _auto_flush; inline bool _isdigit(char c) { return (c & 16) && c != EOF; } inline bool _isgraph(char c) { return c > 32 && c != EOF; }
template <class T> INLINE_V constexpr bool _is_integer = numeric_limits<T>::is_integer; template <class T> INLINE_V constexpr bool _is_signed = numeric_limits<T>::is_signed; template <class T> INLINE_V constexpr bool _is_unsigned = _is_integer<T> && !_is_signed<T>;
template <> INLINE_V constexpr bool _is_integer<__int128> = true; template <> INLINE_V constexpr bool _is_integer<__uint128_t> = true; template <> INLINE_V constexpr bool _is_signed<__int128> = true; template <> INLINE_V constexpr bool _is_unsigned<__uint128_t> = true;
inline void read(char &c) { do c = gc(); while (!_isgraph(c)); } inline void read_cstr(char *s) { char c = gc(); while (!_isgraph(c)) c = gc(); while (_isgraph(c)) *s++ = c, c = gc(); *s = 0; } inline void read(string &s) { char c = gc(); s.clear(); while (!_isgraph(c)) c = gc(); while (_isgraph(c)) s.push_back(c), c = gc(); }
template <class T, enable_if_t<_is_signed<T>, int> = 0> inline void read(T &x) { char c = gc(); bool f = true; x = 0; while (!_isdigit(c)) { if (c == 45) f = false; c = gc(); }
if (f) while (_isdigit(c)) x = x * 10 + (c & 15), c = gc(); else while (_isdigit(c)) x = x * 10 - (c & 15), c = gc(); } template <class T, enable_if_t<_is_unsigned<T>, int> = 0> inline void read(T &x) { char c = gc(); while (!_isdigit(c)) c = gc(); x = 0; while (_isdigit(c)) x = x * 10 + (c & 15), c = gc(); }
inline void write(char c) { pc(c); } inline void write_cstr(const char *s) { while (*s) pc(*s++); } inline void write(const string &s) { for (char c : s) pc(c); } template <class T, enable_if_t<_is_signed<T>, int> = 0> inline void write(T x) { char buffer[numeric_limits<T>::digits10 + 1]; int digits = 0; if (x >= 0) do buffer[digits++] = (x % 10) | 48, x /= 10; while (x);
else { pc(45); do buffer[digits++] = -(x % 10) | 48, x /= 10; while (x); } while (digits) pc(buffer[--digits]); } template <class T, enable_if_t<_is_unsigned<T>, int> = 0> inline void write(T x) { char buffer[numeric_limits<T>::digits10 + 1]; int digits = 0; do buffer[digits++] = (x % 10) | 48, x /= 10; while (x); while (digits) pc(buffer[--digits]); }
template <int N> struct _tuple_io_helper { template <class... T> static inline void _read(tuple<T...> &x) { _tuple_io_helper<N - 1>::_read(x), read(get<N - 1>(x)); } template <class... T> static inline void _write(const tuple<T...> &x) { _tuple_io_helper<N - 1>::_write(x), pc(32), write(get<N - 1>(x)); } };
template <> struct _tuple_io_helper<1> { template <class... T> static inline void _read(tuple<T...> &x) { read(get<0>(x)); } template <class... T> static inline void _write(const tuple<T...> &x) { write(get<0>(x)); } };
template <class... T> inline void read(tuple<T...> &x) { _tuple_io_helper<sizeof...(T)>::_read(x); } template <class... T> inline void write(const tuple<T...> &x) { _tuple_io_helper<sizeof...(T)>::_write(x); }
template <class T1, class T2> inline void read(pair<T1, T2> &x) { read(x.first), read(x.second); } template <class T1, class T2> inline void write(const pair<T1, T2> &x) { write(x.first), pc(32), write(x.second); }
template <class T1, class... T2> inline void read(T1 &x, T2 &...y) { read(x), read(y...); } template <class... T> inline void read_cstr(char *x, T *...y) { read_cstr(x), read_cstr(y...); }
template <class T1, class... T2> inline void write(const T1 &x, const T2 &...y) { write(x), write(y...); } template <class... T> inline void write_cstr(const char *x, const T *...y) { write_cstr(x), write_cstr(y...); }
template <class T> inline void print(const T &x) { write(x); } inline void print_cstr(const char *x) { write_cstr(x); } template <class T1, class... T2> inline void print(const T1 &x, const T2 &...y) { print(x), pc(32), print(y...); }
template <class... T> inline void print_cstr(const char *x, const T *...y) { print_cstr(x), pc(32), print_cstr(y...); } inline void println() { pc(10); } inline void println_cstr() { pc(10); }
template <class... T> inline void println(const T &...x) { print(x...), pc(10); } template <class... T> inline void printk(const T &...x) { print(x...), pc(32); } template <class... T> inline void println_cstr(const T *...x) { print_cstr(x...), pc(10); } } using namespace FastIO;
#define READ(a, n) for(int i = 1; i <= (n); ++ i) read(a[i]);

const int N = 1e5 + 10;
int n, p[N];
ll id[N];
ll nid[N];
ll k;

int bit[N];
void add(int x, int v){
	while(x <= n){
		bit[x] += v;
		x += x & -x;
	}
}
int ask(int x){
	int rs = 0;
	while(x){
		rs += bit[x];
		x -= x & -x;
	}
	return rs;
}
int ask(int l, int r){
	return ask(r) - ask(l-1);
}

const int P = 1e9 + 7;
template<int mod>
inline unsigned int down(unsigned int x) {
  return x >= mod ? x - mod : x;
}
template<int mod>
struct Modint {
  unsigned int x;
  Modint() = default;
  Modint(unsigned int x) : x(x) {}
  friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
  friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
  friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
  friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
  friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
  friend Modint operator/(Modint a, Modint b) {return a * ~b;}
  friend Modint operator^(Modint a, int b) {
    Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
  friend Modint operator~(Modint a) {return a ^ (mod - 2);}
  friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
  friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
  friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
  friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
  friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
  friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
  friend Modint& operator++(Modint& a) {return a += 1;}
  friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
  friend Modint& operator--(Modint& a) {return a -= 1;}
  friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
  friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
  friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};
Modint<P> fac[N], i4;

Modint<P> cal(int n){
	return fac[n] * n * (n-1) * i4;
}

Modint<P> sv(ll x[]){
	Modint<P> ans = 0;
	static Modint<P> ff[N];
	ff[n+1] = 0;
	for(int i = n; i >= 1; -- i){
		ff[i] = ff[i+1] + x[i] * fac[n-i];
	}
	for(int i = 1; i < n; ++ i){
		Modint<P> tmp = 0;
		tmp += x[i] * (x[i]-1) / 2 % P;
		tmp *= fac[n-i];
		tmp += cal(n-i) * x[i];
		tmp += x[i] * ff[i+1];
		ans += tmp;
	}
	return cal(n) - ans; 
}

int main(){
	i4 = 4;
	i4 = ~ i4;
	read(n, k);
	READ(p, n);
	fac[0] = 1;
	for(int i = 1; i <= n; ++ i){
		add(p[i], 1);
		id[i] = p[i] - ask(p[i]);
		fac[i] = fac[i-1] * i;
	}
	for(int i = 1; i <= n; ++ i){
		nid[i] = id[i];
	}
	for(int i = n-1; i >= 1; -- i){
		nid[i] += k % (n - i + 1);
		k /= (n - i + 1);
		if(nid[i] > n - i){
			nid[i-1] += (nid[i] / (n - i +1));
			nid[i] %= (n - i + 1);
		}
		if(!k) break;
	}
	nid[0] += k;
	Modint<P> ans = nid[0] % P;
	ans *= cal(n);
	ans += sv(id);
	ans -= sv(nid);
	println(ans.x);
	return 0;
}
0