結果
問題 | 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";}