結果
問題 | No.1193 Penguin Sequence |
ユーザー | sak |
提出日時 | 2021-01-06 03:33:43 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,116 bytes |
コンパイル時間 | 2,535 ms |
コンパイル使用メモリ | 216,124 KB |
実行使用メモリ | 29,516 KB |
最終ジャッジ日時 | 2024-11-06 11:12:11 |
合計ジャッジ時間 | 21,753 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 360 ms
21,284 KB |
testcase_12 | AC | 365 ms
21,368 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 416 ms
16,768 KB |
testcase_17 | AC | 11 ms
11,060 KB |
testcase_18 | AC | 53 ms
12,540 KB |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | AC | 408 ms
19,936 KB |
testcase_22 | AC | 65 ms
13,092 KB |
testcase_23 | AC | 322 ms
20,528 KB |
testcase_24 | AC | 271 ms
17,572 KB |
testcase_25 | AC | 123 ms
15,216 KB |
testcase_26 | AC | 37 ms
12,324 KB |
testcase_27 | WA | - |
testcase_28 | AC | 377 ms
19,396 KB |
testcase_29 | WA | - |
testcase_30 | AC | 179 ms
16,504 KB |
testcase_31 | AC | 146 ms
15,824 KB |
testcase_32 | AC | 437 ms
24,756 KB |
testcase_33 | AC | 296 ms
17,876 KB |
testcase_34 | AC | 240 ms
18,644 KB |
testcase_35 | AC | 295 ms
19,964 KB |
testcase_36 | AC | 235 ms
18,512 KB |
testcase_37 | WA | - |
testcase_38 | AC | 11 ms
10,968 KB |
testcase_39 | AC | 12 ms
11,212 KB |
testcase_40 | AC | 12 ms
11,132 KB |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<ll, ll> p_ll;template<class T>void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }#define repr(i,from,to) for (ll i=(ll)from; i<(ll)to; i++)#define all(vec) vec.begin(), vec.end()#define rep(i,N) repr(i,0,N)#define per(i,N) for (int i=(int)N-1; i>=0; i--)const ll MOD = 998244353;const ll LLINF = pow(2,61)-1;const int INF = pow(2,30)-1;vector<ll> fac;void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }ll modpow(ll x, ll p) { ll result = 1, now = 1, pm = x; while (now<=p) { if (p&now) { result = result * pm % MOD; } now*=2; pm = pm*pm % MOD; } returnresult; }ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }ll nck(ll n, ll k) { return k<0||k>n ? 0 : fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }// ----------------------------------------------------------------------// ----------------------------------------------------------------------struct SegTree {ll size;vector<ll> pos;SegTree(ll N) { size = 1; while(size<N) size<<=1; pos.resize(2*size,0); }ll operator[](const ll &x) const { return pos[x+size]; }void set(ll x, const ll v) { pos[x+size] = v; }void update(ll x, const ll v) { set(x,v); x+=size; while (x>>=1) operate(x); }ll query(ll a, ll b) {ll L = 0, R = 0;for (a+=size, b+=size; a<b; a>>=1, b>>=1) {if (a&1) { L = q(L,pos[a]); a++; }if (b&1) { b--; R = q(pos[b],R); }}return q(L,R);}void operate(ll i) { pos[i] = q(pos[i*2], pos[i*2+1]); }ll q(ll x, ll y) { return x + y; }};// ----------------------------------------------------------------------// ----------------------------------------------------------------------vector<ll> zaatsu(vector<ll> &list) {map<ll, ll> num; for (auto x: list) num[x]++;ll p = 0; for (auto x: num) { num[x.first] = p; p++; }vector<ll> result; for (auto x: list) result.push_back(num[x]);return result;}// ----------------------------------------------------------------------// ----------------------------------------------------------------------int main() {ll N; cin >> N;vector<ll> A(N); rep(i,N) cin >> A[i];A = zaatsu(A);// debug(all(A));SegTree st(N);ll ten = 0; rep(i,N) { ten += st.query(A[i]+1,N); st.update(A[i],st[A[i]]+1); }ll later = 0; rep(i,N) later = (later+st[i]*st.query(i+1,N)) % MOD;// cout << ten << " " << later << endl;c_fac();ll allc = 1; rep(i,N) allc = allc * nck(N,i+1) % MOD;ll invn2 = modpow(inv(N),2);ll res1 = 0, res2 = 0;rep(i,N) {ll c1 = i+1, c2 = (i+2+N)*(N-(i+1))/2;res1 = (res1+allc*invn2%MOD*c1%MOD*c2%MOD*later%MOD) % MOD;res2 = (res2+allc*inv(nck(N,i+1))%MOD*nck(N-2,i-1)%MOD*ten%MOD) % MOD;}ll result = (res1+res2) % MOD;cout << result << endl;return 0;}