結果

問題 No.2635 MST on Line++ 2
ユーザー maksimmaksim
提出日時 2024-02-16 21:56:07
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 284 ms / 2,000 ms
コード長 6,264 bytes
コンパイル時間 2,440 ms
コンパイル使用メモリ 189,404 KB
実行使用メモリ 61,400 KB
最終ジャッジ日時 2024-09-28 20:12:01
合計ジャッジ時間 13,806 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 176 ms
44,128 KB
testcase_01 AC 175 ms
44,128 KB
testcase_02 AC 180 ms
44,000 KB
testcase_03 AC 186 ms
44,128 KB
testcase_04 AC 180 ms
44,128 KB
testcase_05 AC 270 ms
60,852 KB
testcase_06 AC 180 ms
44,252 KB
testcase_07 AC 269 ms
60,180 KB
testcase_08 AC 177 ms
44,384 KB
testcase_09 AC 235 ms
53,600 KB
testcase_10 AC 181 ms
44,260 KB
testcase_11 AC 263 ms
59,252 KB
testcase_12 AC 179 ms
44,256 KB
testcase_13 AC 274 ms
61,072 KB
testcase_14 AC 178 ms
44,256 KB
testcase_15 AC 228 ms
53,612 KB
testcase_16 AC 177 ms
44,384 KB
testcase_17 AC 261 ms
58,088 KB
testcase_18 AC 178 ms
44,192 KB
testcase_19 AC 273 ms
60,028 KB
testcase_20 AC 180 ms
44,128 KB
testcase_21 AC 276 ms
60,484 KB
testcase_22 AC 178 ms
44,360 KB
testcase_23 AC 229 ms
53,600 KB
testcase_24 AC 175 ms
44,256 KB
testcase_25 AC 176 ms
44,384 KB
testcase_26 AC 274 ms
61,204 KB
testcase_27 AC 264 ms
58,192 KB
testcase_28 AC 282 ms
61,136 KB
testcase_29 AC 190 ms
44,128 KB
testcase_30 AC 180 ms
44,132 KB
testcase_31 AC 275 ms
61,144 KB
testcase_32 AC 276 ms
61,400 KB
testcase_33 AC 269 ms
59,908 KB
testcase_34 AC 275 ms
61,280 KB
testcase_35 AC 277 ms
61,248 KB
testcase_36 AC 284 ms
61,296 KB
testcase_37 AC 274 ms
61,360 KB
testcase_38 AC 280 ms
61,360 KB
testcase_39 AC 184 ms
44,128 KB
testcase_40 AC 178 ms
44,000 KB
testcase_41 AC 177 ms
44,124 KB
testcase_42 AC 178 ms
44,128 KB
testcase_43 AC 177 ms
44,004 KB
testcase_44 AC 178 ms
44,048 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define app push_back
#define all(x) (x).begin(),(x).end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl;}(#__VA_ARGS__, ":", __VA_ARGS__)
#else
#define debug(...)
#endif
#ifdef LOCAL
#define __int128 long long
#endif // LOCAL
typedef long long ll;
const int p=998244353;
int po(int a,int b) {if(b==0) return 1; if(b==1) return a; if(b%2==0) {int u=po(a,b/2);return (u*1LL*u)%p;} else {int u=po(a,b-1);return (a*1LL*u)%p;}}
int inv(int x) {return po(x,p-2);}
template<int M, int K, int G> struct Fft {
  // 1, 1/4, 1/8, 3/8, 1/16, 5/16, 3/16, 7/16, ...
  int g[1 << (K - 1)];
  Fft() : g() { //if tl constexpr...
    static_assert(K >= 2, "Fft: K >= 2 must hold");
    g[0] = 1;
    g[1 << (K - 2)] = G;
    for (int l = 1 << (K - 2); l >= 2; l >>= 1) {
      g[l >> 1] = (static_cast<long long>(g[l]) * g[l]) % M;
    }
    assert((static_cast<long long>(g[1]) * g[1]) % M == M - 1);
    for (int l = 2; l <= 1 << (K - 2); l <<= 1) {
      for (int i = 1; i < l; ++i) {
        g[l + i] = (static_cast<long long>(g[l]) * g[i]) % M;
      }
    }
  }
  void fft(vector<int> &x) const {
    const int n = x.size();
    assert(!(n & (n - 1)) && n <= 1 << K);
    for (int h = __builtin_ctz(n); h--; ) {
      const int l = 1 << h;
      for (int i = 0; i < n >> 1 >> h; ++i) {
        for (int j = i << 1 << h; j < ((i << 1) + 1) << h; ++j) {
          const int t = (static_cast<long long>(g[i]) * x[j | l]) % M;
          if ((x[j | l] = x[j] - t) < 0) x[j | l] += M;
          if ((x[j] += t) >= M) x[j] -= M;
        }
      }
    }
    for (int i = 0, j = 0; i < n; ++i) {
      if (i < j) std::swap(x[i], x[j]);
      for (int l = n; (l >>= 1) && !((j ^= l) & l); ) {}
    }
  }
  vector<int> convolution(const vector<int> &a, const vector<int> &b) const {
    if(a.empty() || b.empty()) return {};
    const int na = a.size(), nb = b.size();
    int n, invN = 1;
    for (n = 1; n < na + nb - 1; n <<= 1) invN = ((invN & 1) ? (invN + M) : invN) >> 1;
    vector<int> x(n, 0), y(n, 0);
    std::copy(a.begin(), a.end(), x.begin());
    std::copy(b.begin(), b.end(), y.begin());
    fft(x);
    fft(y);
    for (int i = 0; i < n; ++i) x[i] = (((static_cast<long long>(x[i]) * y[i]) % M) * invN) % M;
    std::reverse(x.begin() + 1, x.end());
    fft(x);
    x.resize(na + nb - 1);
    return x;
  }
};
Fft<998244353,23,31> muls;
vector<int> form(vector<int> v,int n)
{
    while(v.size()<n) v.push_back(0);
    while(v.size()>n) v.pop_back();
    return v;
}
vector<int> operator *(vector<int> v1,vector<int> v2)
{
    return muls.convolution(v1,v2);
}
vector<int> operator +(vector<int> v1,vector<int> v2)
{
    while(v2.size()<v1.size()) v2.push_back(0); while(v1.size()<v2.size()) v1.push_back(0);
    for(int i=0;i<v1.size();++i) {v1[i]+=v2[i];if(v1[i]>=p) v1[i]-=p; else if(v1[i]<0) v1[i]+=p;}
    return v1;
}
vector<int> operator -(vector<int> v1,vector<int> v2)
{
    int sz=max(v1.size(),v2.size());while(v1.size()<sz) v1.push_back(0); while(v2.size()<sz) v2.push_back(0);
    for(int i=0;i<sz;++i) {v1[i]-=v2[i];if(v1[i]<0) v1[i]+=p; else if(v1[i]>=p) v1[i]-=p;} return v1;
}
vector<int> trmi(vector<int> v)
{
    for(int i=1;i<v.size();i+=2) {if(v[i]>0) v[i]=p-v[i]; else v[i]=(-v[i]);}
    return v;
}
vector<int> deriv(vector<int> v)
{
    if(v.empty()) return{};
    vector<int> ans(v.size()-1);
    for(int i=1;i<v.size();++i) ans[i-1]=(v[i]*1LL*i)%p;
    return ans;
}
vector<int> integ(vector<int> v)
{
    vector<int> ans(v.size()+1);ans[0]=0;
    for(int i=1;i<v.size();++i) ans[i-1]=(v[i]*1LL*i)%p;
    return ans;
}
vector<int> mul(vector<vector<int> > v)
{
    if(v.size()==1) return v[0];
    vector<vector<int> > v1,v2;for(int i=0;i<v.size()/2;++i) v1.push_back(v[i]); for(int i=v.size()/2;i<v.size();++i) v2.push_back(v[i]);
    return muls.convolution(mul(v1),mul(v2));
}
vector<int> inv1(vector<int> v,int n)
{
    assert(v[0]!=0);
    int sz=1;v=form(v,n);vector<int> a={inv(v[0])};
    while(sz<n)
    {
        vector<int> vsz;for(int i=0;i<min(n,2*sz);++i) vsz.push_back(v[i]);
        vector<int> b=((vector<int>) {1})-muls.convolution(a,vsz);
        for(int i=0;i<sz;++i) assert(b[i]==0);
        b.erase(b.begin(),b.begin()+sz);
        vector<int> c=muls.convolution(b,a);
        for(int i=0;i<sz;++i) a.push_back(c[i]);
        sz*=2;
    }
    return form(a,n);
}
vector<int> inv(vector<int> v,int n)
{
    v=form(v,n);assert(v[0]!=0);if(v.size()==1) {return {inv(v[0])};} vector<int> v1=trmi(v);
    vector<int> a=v1*v;a=form(a,2*n);
    vector<int> b((n+1)/2);for(int i=0;i<b.size();++i) b[i]=a[2*i];
    vector<int> ans1=inv(b,b.size());vector<int> ans2(n);for(int i=0;i<n;++i) {if(i%2==0) ans2[i]=ans1[i/2]; else ans2[i]=0;}
    return form(v1*ans2,n);
}
vector<int> operator/(vector<int> a,vector<int> b)
{
    while(!a.empty() && a.back()==0) a.pop_back(); while(!b.empty() && b.back()==0) b.pop_back();
    int n=a.size();int m=b.size();if(n<m) return {};
    reverse(a.begin(),a.end());reverse(b.begin(),b.end());vector<int> ans=a*inv(b,n-m+1);while(ans.size()>n-m+1) ans.pop_back();
    reverse(ans.begin(),ans.end());while(!ans.empty() && ans.back()==0) ans.pop_back();return ans;
}
vector<int> operator%(vector<int> a,vector <int> b)
{
    vector<int> ans=a-b*(a/b);while(!ans.empty() && ans.back()==0) ans.pop_back(); return ans;
}
const int maxn=5e5+5;
int fact[maxn];int invf[maxn];
int32_t main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    fact[0]=1;for(int i=1;i<maxn;++i) {fact[i]=(fact[i-1]*i)%p;} for(int i=0;i<maxn;++i) {invf[i]=inv(fact[i]);}
    int n,k;cin>>n>>k;
    int a[n];for(int i=0;i<n;++i) cin>>a[i];
    sort(a,a+n);
    vector<int> a1(n);for(int i=0;i<n;++i) {a1[i]=a[i]*fact[n-i-1];a1[i]%=p;}
    vector<int> a2(n+1);for(int i=0;i<=n;++i) {a2[i]=invf[i];a2[i]%=p;}
    int res=0;
    vector<int> lens(n+1);for(int i=-k+1;i<=n-k-1;++i) {int l1=i,r1=i+2*k-1;l1=max(l1,0LL);r1=min(r1,n-1);debug(r1-l1+1);lens[r1-l1+1]++;}
    vector<int> c=a1*a2;
    for(int len=1;len<=n;++len)
    {
        int rl=c[n-len]*invf[len-1];rl%=p;
        debug(len,rl);
        res+=((((rl*lens[len])%p)*fact[n-len])%p)*fact[len];res%=p;
    }
    cout<<(res%p+p)%p;
    return 0;
}
0