結果
問題 | No.2135 C5 |
ユーザー |
![]() |
提出日時 | 2022-11-11 03:50:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 203 ms / 2,000 ms |
コード長 | 1,217 bytes |
コンパイル時間 | 5,228 ms |
コンパイル使用メモリ | 255,196 KB |
最終ジャッジ日時 | 2025-02-08 19:39:21 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 48 |
ソースコード
#include<bits/stdc++.h>#include<atcoder/all>using namespace std;using namespace atcoder;typedef modint998244353 mint;typedef long long ll;//defmodfactconst int COMinitMAX = 500;mint fact[COMinitMAX+1], factinv[COMinitMAX+1];void modfact(){fact[0] = 1;for (int i=1; i<=COMinitMAX; i++){fact[i] = fact[i-1] * i;}factinv[COMinitMAX] = fact[COMinitMAX].inv();for (int i=COMinitMAX-1; i>=0; i--){factinv[i] = factinv[i+1] * (i+1);}}mint cmb(int a, int b){if (a<b || b<0) return mint(0);return fact[a]*factinv[b]*factinv[a-b];}//--------int main(){modfact();int n, m;cin >> n >> m;if (m < n*(n-1)/2 - n){cout << 0 << endl;return 0;}mint inv2 = mint(2).inv();vector<vector<mint>> dp(n+1, vector<mint>(n+1));dp[0][0] = 1;for (int i=0; i<n+1; i++){for (int j=0; j<n+1; j++){if (i+1 <= n) dp[i+1][j] += dp[i][j];for (int k=2; k<=min(n-i, n-j+1); k++){dp[i+k][j+k-1] += cmb(n-i-1, k-1) * dp[i][j] * fact[k] * inv2;}for (int k=5; k<=min(n-i, n-j); k++){dp[i+k][j+k] += cmb(n-i-1, k-1) * dp[i][j] * fact[k-1] * inv2;}}}if (n*(n-1)/2-m <= n){cout << dp[n][n*(n-1)/2-m].val() << endl;}else{cout << 0 << endl;}}