#1171096 (C++23) No.3589 Make Ends Meet (Hard)

• 問題: No.3589 Make Ends Meet (Hard)
• ユーザー: 蜜蜂
• 提出日時: 2026-07-11 01:39:50
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: WA
• 実行時間: -
• コード長: 4,691 bytes
• コンパイル時間: 4,655 ms
• コンパイル使用メモリ: 377,808 KB
• 実行使用メモリ: 216,260 KB
• 最終ジャッジ日時: 2026-07-11 01:40:12
• 合計ジャッジ時間: 19,362 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_0

ファイルパターン	結果
sample	AC * 3
other	AC * 38 WA * 9

ソースコード

// g++-15 1.cpp -std=c++23 -O2 -I .

// 壊れるとき
// conda deactivate    # 何回か必要なことあり
// hash -r             # コマンドキャッシュクリア
// which -a ld
// ld の先頭が /usr/bin/ld になればそのままコンパイルしてOK


#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// #include<ext/pb_ds/tag_and_trait.hpp>
// using namespace __gnu_pbds;

#include <atcoder/convolution>
#include <atcoder/math>
#include <atcoder/modint>
using namespace atcoder;

using ll = long long;
using ld = long double;

using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vst = vector<string>;
using vvst = vector<vst>;

#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pq_big(T) priority_queue<T,vector<T>,less<T>>
#define pq_small(T) priority_queue<T,vector<T>,greater<T>>
#define all(a) a.begin(),a.end()
#define rep(i,start,end) for(ll i=start;i<(ll)(end);i++)
#define per(i,start,end) for(ll i=start;i>=(ll)(end);i--)
#define uniq(a) sort(all(a));a.erase(unique(all(a)),a.end())

template <typename S, typename T>
istream& operator>>(istream& is, pair<S, T> &v){
  is >> v.first >> v.second;
  return is;
}

template <typename S, typename T>
ostream& operator<<(ostream& os, pair<S, T> &v){
  os << v.first << " " << v.second << "\n";
  return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T> &v){
  for(T &e: v) is >> e;
  return is;
}

template <typename T>
ostream& operator<<(ostream& os, vector<T> v){
  if(v.empty()){
    os<<"\n";
    return os;
  }
  for(int i=0;i<v.size()-1;i++)os<<v[i]<<" ";
  os<<v.back()<<"\n";
  return os;
}

random_device seed;
mt19937_64 randint(seed());

ll grr(ll mi, ll ma) { // [mi, ma)
    return mi + randint() % (ma - mi);
}

using mint = modint998244353;

const int MAX=510000;
const long long MOD=998244353;

long long fac[MAX],finv[MAX],inv[MAX];

void COMinit(){
  fac[0]=fac[1]=1;
  finv[0]=finv[1]=1;
  inv[1]=1;
  for(int i=2;i<MAX;i++){
    fac[i]=fac[i-1]*i%MOD;
    inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
    finv[i]=finv[i-1]*inv[i]%MOD;
  }
}

long long COM(int n,int k){
  if(n<k) return 0;
  if(n<0||k<0) return 0;
  return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}

mint dp[40][40][40][800]={};

void solve(){
  int n,m,d;cin>>n>>m>>d;
  int rem=n*(n-1)/2-m;
  // rem 残す
  dp[0][1][1][0]=1;

  vector<vector<vector<mint>>> sub;
  rep(k,1,n+1){
    // 直前に k 個ある
    vector<mint> init(k);
    rep(l,0,k)init[l]=COM(k,(l+1));
    // init[l] := 1 つの距離 i + 1 の頂点から距離 i へ伸ばす
    // l + 1 個繋げる場合の数え上げ
    vector<mint> state={1};
    vector<vector<mint>> dp2={state};
    rep(nxtk,1,n-k+1){
      // ここでは nxtk 個使う
      state=convolution(state,init);
      vector<mint> dp3;
      int edge=nxtk*(nxtk-1)/2;
      rep(add,0,edge+1){
        dp3.emplace_back(COM(edge,add));
      }
      dp2.emplace_back(convolution(state,dp3));
    }
    sub.emplace_back(dp2);
  }

  rep(i,0,n-1){
    // dp[i] -> dp[i+1]
    rep(j,0,n+1){
      rep(k,1,j+1){
        rep(l,j-1,j*(j-1)/2+1){
          if(dp[i][j][k][l].val()==0)continue;
          // cout<<i<<" "<<j<<" "<<k<<" "<<l<<endl;
          rep(nxtk,1,n-j+1){
            rep(addl,0,sub[k-1][nxtk].size()){
              // cout<<nxtk<<" "<<addl<<endl;
              // cout<<sub[k-1][nxtk][addl].val()<<endl;
              mint add=dp[i][j][k][l]*sub[k-1][nxtk][addl];
              if(i+1!=d)add*=finv[nxtk];
              else add*=finv[nxtk-1];
              dp[i+1][j+nxtk][nxtk][l+nxtk+addl]+=add;
              // cout<<"ok "<<nxtk<<" "<<addl<<endl;
            }
          }
          // cout<<"ok "<<i<<" "<<j<<" "<<k<<" "<<l<<endl;
        }
      }
    }
  }
  // cout<<"dp calc end"<<endl;

  mint ans=0;
  rep(i,d,n){
    // max の距離が i です
    rep(j,0,n+1){
      // total j 個
      rep(k,0,n+1){
        rep(l,0,rem+1){
          if(dp[i][j][k][l].val()==0)continue;
          // 連結でないのは n - j ある
          int edge=(n-j)*(n-j-1)/2;
          ans+=dp[i][j][k][l]*COM(edge,rem-l);
        }
      }
    }
  }
  ans*=fac[n-2];
  cout<<ans.val()<<endl;
}

/*
dp[i][j][k][l] := 
距離 i まで決めた j 個頂点を使った 距離 i では k 個存在
合計 l 本辺を使いました
N, N, N, N^2
*/

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  COMinit();
  
  int t=1;
  // cin>>t;
  while(t--){
    solve();
  }
}