結果
問題 | No.2635 MST on Line++ 2 |
ユーザー |
👑 ![]() |
提出日時 | 2024-02-11 16:07:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,568 bytes |
コンパイル時間 | 2,182 ms |
コンパイル使用メモリ | 203,244 KB |
最終ジャッジ日時 | 2025-02-19 05:08:24 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 20 RE * 21 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;#define rep(i,a,b) for(int i=int(a);i<int(b);i++)struct mint{static constexpr int m = 998244353;int x;mint() : x(0){}mint(ll x_):x(x_%m){if(x<0)x+=m;}mint &operator+=(mint b){if((x+=b.x)>=m)x-=m; return *this;}mint &operator-=(mint b){if((x-=b.x)<0)x+=m; return *this;}mint &operator*=(mint b){x=ll(x)*b.x%m; return *this;}mint pow(ll e) const {mint r = 1,b =*this;while(e){if(e&1) r*=b;b*=b;e>>=1;}return r;}mint inv(){return pow(m-2);}mint &operator/=(mint b){return *this*=b.pow(m-2);}friend mint operator+(mint a,mint b){return a+=b;}friend mint operator-(mint a,mint b){return a-=b;}friend mint operator/(mint a,mint b){return a/=b;}friend mint operator*(mint a,mint b){return a*=b;}};int main(){ios::sync_with_stdio(false);cin.tie(nullptr);ll N,K;cin>>N>>K;vector<ll> A(N);rep(i,0,N) cin>>A[i];assert(N<=7000);sort(A.begin(),A.end());auto D=A;for(int i=N-1;i>0;i--) D[i]-=D[i-1];vector<mint> fact(N+1,1),fact_inv(N+1,1);rep(i,0,N) fact[i+1]=fact[i]*(i+1);fact_inv[N]=fact[N].inv();for(int i=N;i>0;i--) fact_inv[i-1]=fact_inv[i]*i;auto P=[&](ll a,ll b) -> mint {if(a<b||a<0) return 0;return fact[a]*fact_inv[a-b];};mint ans=0;rep(i,0,N-1){int a=0;rep(j,0,N){if(K<=min(abs(j-i),abs(j-i-1))) a++;}rep(j,0,N){ans+=P(a,j)*fact[N-j]*mint(D[j]);}}cout<<ans.x<<"\n";}