結果
問題 | No.2635 MST on Line++ 2 |
ユーザー |
👑 ![]() |
提出日時 | 2024-02-16 20:53:39 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 3,866 bytes |
コンパイル時間 | 2,319 ms |
コンパイル使用メモリ | 208,720 KB |
最終ジャッジ日時 | 2025-02-19 13:32:13 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 6 RE * 35 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define rep(i,a,b) for(int i=a;i<b;i++)struct mint{static constexpr int m = 998244353;int x;mint() : x(0){}mint(long long x_):x(x_%m){if(x<0)x+=m;}int val(){return x;}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=(long long)(x)*b.x%m; return *this;}mint pow(long long 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;}friend bool operator==(mint a,mint b){return a.x==b.x;}friend bool operator!=(mint a,mint b){return a.x!=b.x;}};namespace po167{template<class T>struct Binomial{std::vector<T> fact_vec, fact_inv_vec;void extend(int m = -1){int n = fact_vec.size();if (m == -1) m = n * 2;if (n >= m) return;fact_vec.resize(m);fact_inv_vec.resize(m);for (int i = n; i < m; i++){fact_vec[i] = fact_vec[i - 1] * T(i);}fact_inv_vec[m - 1] = T(1) / fact_vec[m - 1];for (int i = m - 1; i > n; i--){fact_inv_vec[i - 1] = fact_inv_vec[i] * T(i);}}Binomial(int MAX = 2){fact_vec.resize(1, T(1));fact_inv_vec.resize(1, T(1));extend(MAX + 1);}T fact(int i){if (i < 0) return 0;while (int(fact_vec.size()) <= i) extend();return fact_vec[i];}T invfact(int i){if (i < 0) return 0;while (int(fact_inv_vec.size()) <= i) extend();return fact_inv_vec[i];}T C(int a, int b){if (a < b || b < 0) return 0;return fact(a) * invfact(b) * invfact(a - b);}T P(int a, int b){if (a < b || b < 0) return 0;return fact(a) * invfact(a - b);}T inv(int a){if (a < 0) return inv(-a) * T(-1);if (a == 0) return 1;return fact(a - 1) * invfact(a);}};}namespace po167{struct UFtree{using _F=int;int _n;std::vector<_F> wei;std::vector<int> q;int component;UFtree(int n):_n(n),wei(n),component(n),par(n){for(int i=0;i<n;i++){wei[i]=1,par[i]=i;}}void intialize(){for(auto x:q){wei[root(x)]=1;par[x]=x;}component=(int)par.size();q={};}//根っこを返すint root(int a){assert(0<=a&&a<_n);if(a==par[a]) return a;return par[a]=root(par[a]);}//trueなら1,falseなら0int same(int a,int b){assert(0<=a&&a<_n);assert(0<=b&&b<_n);if(root(a)==root(b)) return 1;else return 0;}_F size(int a){return wei[root(a)];}//a,bが違う根っこの元なら結合する,結合したらtrueを返すbool unite(int a,int b){a=root(a),b=root(b);if(a==b) return false;if(wei[a]<wei[b]) std::swap(a,b);par[b]=a;q.push_back(b);wei[a]+=wei[b];component--;return true;}private:std::vector<int> par;};}using po167::UFtree;int main(){int N,K;cin>>N>>K;po167::Binomial<mint> table;mint ans=0;vector<int> A(N);rep(i,0,N) cin>>A[i];sort(A.begin(),A.end());assert(N<=20);auto f=[&](UFtree &t,int ind) -> int {int res=0;rep(i,0,N){if(abs(i-ind)<=K) if(t.unite(i,ind)) res++;}return res;};rep(x,0,(1<<N)-1){UFtree T(N);int a=0;rep(i,0,N) if(x&(1<<i)) f(T,i),a++;rep(i,0,N) if((x&(1<<i))==0){auto S=T;ans+=mint(A[a])*f(S,i)*table.fact(N-a-1)*table.fact(a);}}cout<<ans.val()<<"\n";}