結果
問題 | No.1193 Penguin Sequence |
ユーザー | sak |
提出日時 | 2021-01-06 03:40:02 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,128 bytes |
コンパイル時間 | 2,528 ms |
コンパイル使用メモリ | 214,768 KB |
実行使用メモリ | 29,640 KB |
最終ジャッジ日時 | 2024-11-06 11:18:13 |
合計ジャッジ時間 | 22,974 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 381 ms
21,032 KB |
testcase_12 | AC | 375 ms
21,172 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 424 ms
16,648 KB |
testcase_17 | AC | 11 ms
11,088 KB |
testcase_18 | AC | 55 ms
12,528 KB |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | AC | 436 ms
19,980 KB |
testcase_22 | AC | 66 ms
12,948 KB |
testcase_23 | AC | 345 ms
20,520 KB |
testcase_24 | AC | 297 ms
17,508 KB |
testcase_25 | AC | 128 ms
14,944 KB |
testcase_26 | AC | 38 ms
12,096 KB |
testcase_27 | WA | - |
testcase_28 | AC | 381 ms
19,456 KB |
testcase_29 | WA | - |
testcase_30 | AC | 186 ms
16,304 KB |
testcase_31 | AC | 150 ms
15,624 KB |
testcase_32 | AC | 472 ms
24,792 KB |
testcase_33 | AC | 313 ms
17,668 KB |
testcase_34 | AC | 243 ms
18,600 KB |
testcase_35 | AC | 312 ms
19,900 KB |
testcase_36 | AC | 241 ms
18,416 KB |
testcase_37 | WA | - |
testcase_38 | AC | 11 ms
11,092 KB |
testcase_39 | AC | 11 ms
11,016 KB |
testcase_40 | AC | 11 ms
11,040 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 = (ten+st.query(A[i]+1,N)) % MOD; 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;}