結果
問題 |
No.2635 MST on Line++ 2
|
ユーザー |
👑 ![]() |
提出日時 | 2024-02-13 05:55:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 78 ms / 2,000 ms |
コード長 | 1,388 bytes |
コンパイル時間 | 4,742 ms |
コンパイル使用メモリ | 272,400 KB |
最終ジャッジ日時 | 2025-02-19 05:51:08 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> #pragma GCC optimize("unroll-loops") using namespace std; const int mod=998244353; #define rep(i,a,b) for (int i=int(a);i<int(b);i++) #include<atcoder/all> using namespace atcoder; using mint=modint998244353; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N,K; cin>>N>>K; vector<int> A(N); rep(i,0,N) cin>>A[i]; sort(A.begin(),A.end()); vector<mint> D(N); rep(i,0,N) D[i]=A[i]; for(int i=N-1;i>0;i--) D[i]-=D[i-1]; vector<mint> fact(N+2,1),fact_inv(N+2,1); rep(i,0,N+1) fact[i+1]=fact[i]*(i+1); fact_inv[N+1]=fact[N+1].inv(); for(int i=N+1;i>0;i--) fact_inv[i-1]=fact_inv[i]*i; auto P=[&](int a,int b) -> mint { if(a<0||a<b) return 0; return fact[a]*fact_inv[a-b]; }; auto C=[&](int a,int b) -> mint { if(a<0||a<b) return 0; return fact[a]*fact_inv[b]*fact_inv[a-b]; }; auto f=[&](int a) -> mint { mint res=0; rep(j,0,N){ res+=P(a,j)*D[j]*fact[N-j]; } return res; }; // f(l)+f(l+1)+...+f(r) auto g=[&](int l,int r) -> mint { mint res=0; rep(k,0,N){ res+=D[k]*fact[N-k]*fact[k]*(C(r+1,k+1)-C(l,k+1)); } return res; }; mint ans=0; map<int,int> m; int L=N+1,R=-1; rep(i,1,N){ m[N-min(i,K)-min(N-i,K)]++; } for(auto x:m){ if(x.second!=2) ans+=f(x.first)*x.second; else{ L=min(L,x.first); R=max(R,x.first); } } if(L<=R) ans+=g(L,R)*2; cout<<ans.val()<<"\n"; }