結果
| 問題 |
No.1193 Penguin Sequence
|
| コンテスト | |
| ユーザー |
 Chanyuh
|
| 提出日時 | 2020-08-23 16:20:33 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,486 bytes |
| コンパイル時間 | 2,572 ms |
| コンパイル使用メモリ | 137,304 KB |
| 最終ジャッジ日時 | 2025-01-13 12:36:25 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 6 WA * 32 |
ソースコード
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
#include<cassert>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 998244353;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
template<int mod>
struct ModInt {
long long x;
ModInt() : x(0) {}
ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
explicit operator int() const {return x;}
ModInt &operator+=(const ModInt &p) {
if((x += p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator-=(const ModInt &p) {
if((x += mod - p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator*=(const ModInt &p) {
x = (int)(1LL * x * p.x % mod);
return *this;
}
ModInt &operator/=(const ModInt &p) {
*this *= p.inverse();
return *this;
}
ModInt operator-() const { return ModInt(-x); }
ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
bool operator==(const ModInt &p) const { return x == p.x; }
bool operator!=(const ModInt &p) const { return x != p.x; }
ModInt inverse() const{
int a = x, b = mod, u = 1, v = 0, t;
while(b > 0) {
t = a / b;
a -= t * b;
swap(a, b);
u -= t * v;
swap(u, v);
}
return ModInt(u);
}
ModInt power(long long p) const{
int a = x;
if (p==0) return 1;
if (p==1) return ModInt(a);
if (p%2==1) return (ModInt(a)*ModInt(a)).power(p/2)*ModInt(a);
else return (ModInt(a)*ModInt(a)).power(p/2);
}
ModInt power(const ModInt p) const{
return ((ModInt)x).power(p.x);
}
friend ostream &operator<<(ostream &os, const ModInt<mod> &p) {
return os << p.x;
}
friend istream &operator>>(istream &is, ModInt<mod> &a) {
long long x;
is >> x;
a = ModInt<mod>(x);
return (is);
}
};
using modint = ModInt<mod>;
template <typename T>
struct SegmentTree{
using F = function<T(T,T)>;
int n;
F f;//二項演算
T ti;//単位元
vector<T> dat;
SegmentTree(){}
SegmentTree(F f,T ti):f(f),ti(ti){}
void init(int n_){//sizeがn_のsegtreeを作る
n=1;
while(n<n_) n<<=1;
dat.assign(n<<1,ti);
}
void build(const vector<T> &v){//vによってsegtreeをbuildする
int n_=v.size();
init(n_);
for(int i=0;i<n_;i++) dat[n+i]=v[i];
for(int i=n-1;i;i--)
dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
}
void set_val(int k,T x){//k番目をxにする
dat[k+=n]=x;
while(k>>=1)
dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
}
T query(int a,int b){//区間[a,b)に対しFを適応した値を返す
if(a>=b) return ti;
T vl=ti,vr=ti;
for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
if(l&1) vl=f(vl,dat[l++]);
if(r&1) vr=f(dat[--r],vr);
}
return f(vl,vr);
}
template<typename C>
int find(int st,C &check,T &acc,int k,int l,int r){//
if(l+1==r){
acc=f(acc,dat[k]);
return check(acc)?k-n:-1;
}
int m=(l+r)>>1;
if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);
if(st<=l&&!check(f(acc,dat[k]))){
acc=f(acc,dat[k]);
return -1;
}
int vl=find(st,check,acc,(k<<1)|0,l,m);
if(~vl) return vl;
return find(st,check,acc,(k<<1)|1,m,r);
}
template<typename C>
int find(int st,C &check){
T acc=ti;
return find(st,check,acc,1,0,n);
}
T &operator [] (int i) {return dat[i+n];};
};
struct ModFac{
public:
vector<modint> f,i_f;
int n;
ModFac(int n_){
n=n_;
f.resize(n+1,1);
i_f.resize(n+1,1);
for(int i=0;i<n;i++){
f[i+1]=f[i]*(modint)(i+1);
}
i_f[n]=f[n].power(mod-2);
for(int i=n-1;i>=0;i--){
i_f[i]=i_f[i+1]*(modint)(i+1);
}
}
ModFac(modint n_){
n=(int)n_;
f.resize(n+1,1);
i_f.resize(n+1,1);
for(int i=0;i<n;i++){
f[i+1]=f[i]*(modint)(i+1);
}
i_f[n]=f[n].power(mod-2);
for(int i=n-1;i>=0;i--){
i_f[i]=i_f[i+1]*(modint)(i+1);
}
}
modint factorial(int x){
//cout << f.size() << endl;
return f[x];
}
modint inv_factorial(int x){
return i_f[x];
}
modint comb(int m,int k){
if (m<0 or k<0) return 0;
if (m<k) return 0;
return f[m]*i_f[k]*i_f[m-k];
}
};
int n;
int a[200010];
vector<int> zaatu;
ModFac MF(1000010);
void solve(){
cin >> n;
rep(i,n){
cin >> a[i];
zaatu.push_back(a[i]);
}
sort(zaatu.begin(),zaatu.end());
rep(i,n){
a[i]=lower_bound(zaatu.begin(),zaatu.end(),a[i])-zaatu.begin();
}
auto f=[](ll a,ll b){return a+b;};
SegmentTree<ll> seg(f,0);
seg.init(n+1);
ll inv=0;
rep(i,n){
inv+=seg.query(a[i]+1,n+1);
seg.set_val(a[i],seg[a[i]]+1);
}
//cout << inv << endl;
modint p=0;
rep(i,n){
p+=lower_bound(zaatu.begin(),zaatu.end(),zaatu[i])-zaatu.begin();
}
//cout << p << endl;
modint T=p/(n*n),S=0;
rep(i,n+1){
modint i_=i;
S+=i_*i_*i_-i_*i_;
}
S/=2;
//cout << S << endl;
modint ans=T*S;
Rep(k,1,n+1){
ans+=MF.comb(n-2,k-2)/MF.comb(n,k)*(modint)inv;
}
Rep(k,1,n+1){
ans*=MF.comb(n,k);
}
cout << ans << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(50);
solve();
}