結果
問題 | No.1193 Penguin Sequence |
ユーザー |
![]() |
提出日時 | 2020-08-22 17:17:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 328 ms / 2,000 ms |
コード長 | 2,791 bytes |
コンパイル時間 | 2,670 ms |
コンパイル使用メモリ | 207,628 KB |
最終ジャッジ日時 | 2025-01-13 10:35:15 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 38 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define modulo 998244353 #define mod(mod_x) ((((long long)mod_x+modulo))%modulo) #define Inf 1000000005 int beki(long long a,long long b,int M = modulo){ int x = 1; while(b!=0){ if(b&1){ x=((long long)x*a)%M; } a=((long long)a*a)%M; b>>=1; } return x; } int gyakugen(int a){ return beki(a,modulo-2); } struct combi{ deque<int> kaijou; deque<int> kaijou_; combi(int n){ kaijou.push_back(1); for(int i=1;i<=n;i++){ kaijou.push_back(mod(kaijou[i-1]*i)); } int b=gyakugen(kaijou[n]); kaijou_.push_front(b); for(int i=1;i<=n;i++){ int k=n+1-i; kaijou_.push_front(mod(kaijou_[0]*k)); } } int combination(int n,int r){ if(r>n)return 0; int a = mod(kaijou[n]*kaijou_[r]); a=mod(a*kaijou_[n-r]); return a; } int junretsu(int a,int b){ int x = mod(kaijou_[a]*kaijou_[b]); x=mod(x*kaijou[a+b]); return x; } int catalan(int n){ return mod(combination(2*n,n)*gyakugen(n+1)); } }; template <typename T> struct BIT{ vector<T> v; int n; T init_value = 0; BIT(int sz=0){ n=sz+1; v.resize(n,init_value); } BIT(vector<T> &x){ n=x.size()+1; v.resize(n,init_value); for(int i=0;i<x.size();i++){ add(i,x[i]); } } void add(int x,T val){ x++; while(x < n){ v[x] = func(v[x],val); x += x & (-x); } } //区間[0,r)におけるクエリ処理 T query(int r){ T ret = init_value; while(r>0){ ret = func(v[r],ret); r -= r & (-r); } return ret; } T query(int l,int r){ return mod(query(r) - query(l)); } T func(T a,T b){ return mod(a+b); } int size(){ return n-1; } }; int main(){ int N; cin>>N; if(N==1){ cout<<0<<endl; return 0; } vector<int> A(N); for(int i=0;i<N;i++)cin>>A[i]; int sum = 0; { vector<int> t = A; sort(t.begin(),t.end()); t.erase(unique(t.begin(),t.end()),t.end()); for(int i=0;i<N;i++){ A[i] = distance(t.begin(),lower_bound(t.begin(),t.end(),A[i])); } vector<int> B = A; sort(B.begin(),B.end()); for(int i=0;i<N;i++){ sum = mod(sum + distance(upper_bound(B.begin(),B.end(),A[i]),B.end())); } } int ans = 0; combi C(1000000); int S = 1; for(int i=1;i<=N;i++){ S = mod(S * C.combination(N,i)); } int t = 0; for(int i=1;i<=N;i++){ int x = mod(C.combination(N-1,i-1)*gyakugen(C.combination(N,i))); int y = mod(x); y = mod(y * S); y = mod(y * sum); ans = mod(ans + mod(y*t)); t = mod(t + x); } int B = 0; { BIT<int> b(N); for(int i=0;i<N;i++){ B = mod(B + b.query(A[i]+1,N)); b.add(A[i],1); } } for(int i=2;i<=N;i++){ int x = mod(S * gyakugen(C.combination(N,i))); x = mod(x * C.combination(N-2,i-2)); ans = mod(ans + mod(B*x)); } cout<<ans<<endl; return 0; }