# AtCoder Regular Contest 163 (D)
> https://atcoder.jp/contests/arc163/tasks/arc163_d

這題對筆者而言很新鮮很有趣，但被輾爛是必然，故筆記一下。
題意為考慮所有$N$個點的競賽圖(Tournament)且有剛好$M$條index從小連到大的邊，問說這些競賽圖中全部強連通塊的總數。$1 \leq N \leq 30$， $0 \leq M \leq C^N_2$。

競賽圖有個性質是圖中的SCC縮點後，整個圖變成一條鏈狀DAG(以下方便都簡稱鏈)：
> https://www.cnblogs.com/A-Quark/p/16410007.html
>
這邊用歸納法說明個大概，假如$i$點競賽圖縮點後為鏈，考慮加入第$i+1$點，則大概有以下3種情況：
(1) 所有邊都連向$1 \sim i$，則把$i+1$放到最左邊原圖為鏈。
(2) 所有邊都連回$i+1$，則把$i+1$放到最右邊原圖為鏈。
(3) 剩餘情況可以考慮最右邊之連回$i+1$的邊和最左邊連向$1 \sim i$的邊，可以發現中間這些SCC和$i+1$會縮成一個SCC。

於是我們要在所有這些鏈中算出點的總數，且滿足剛好有$M$條index小到大邊，考慮用DP想。
如果我們考慮狀態之SCC總數感覺會很難，因為每次加入新點後SCC可能變大也可能變小，於是參考解答一下，如果我們僅考慮狀態為將鏈分割成左右兩邊的話，且左右兩邊可以為空集，則鏈中的SCC總數就是鏈的分割總數減一，這表示說我們最後求得的全部鏈分割總數減去所有可能的鏈就得所求，所有滿足條件的競賽圖為$C^{邊數}_M$。

定義$dp(i, j, k)$為考慮$1 \sim i$點且鏈分割左邊有$j$點且共有$k$條index從小到大邊，的所有情況總數，考慮第$i+1$點放在左邊或是右邊，
(1) 放左邊且左邊有$l$條邊連到$i+1$：
\begin{array}{ll}
dp(i, j, k) \times C^j_l \rightarrow dp(i+1, j+1, k+l),\ if(0 \leq l \leq j)
\end{array}

(2) 放右邊且右邊有$l$條邊連到$i+1$：
\begin{array}{ll}
dp(i, j, k) \times C^{i-j}_l \rightarrow dp(i+1, j, k+i+l),\ if(0 \leq l \leq i-j)
\end{array}

最後所求為$\sum_{j=0}^{n} dp(n, j, m) - C^{N(N-1)/2}_M$。

#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define F first
#define S second
#define endl '\n'
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int N = 2e3 + 5;

const int maxn = 2e4 + 5;

ll fac[maxn], inv[maxn];
void init(){
    fac[0] = fac[1] = inv[0] = inv[1] = 1;
    for(int i=2; i<maxn; i++){
        fac[i] = (i * fac[i-1]) % mod;
        inv[i] = mod - mod/i * inv[mod%i] % mod;
    }
    for(int i=2; i<maxn; i++){
        inv[i] = (inv[i] * inv[i-1]) % mod; 
    }

    return;
}

ll C(int n, int k){
    if(n < k || k < 0 || n < 0) return 0;
    return fac[n] * inv[k] % mod * inv[n-k] % mod;
}

ll dp[31][31][31*31];

void solve(){
    ll n, m; cin >> n >> m;
    if(n == 1){
        cout << 1 << endl;
        return;
    }
    memset(dp, 0, sizeof dp);
    dp[1][1][0] = dp[1][0][0] = 1;
    for(int i=1; i<n; i++){
        for(int j=0; j<=i; j++){
            for(int k=0; k<=i*(i-1)/2; k++){
                if(!dp[i][j][k]) continue;
                for(int l=0; l<=j; l++) dp[i+1][j+1][k+l] = (dp[i+1][j+1][k+l] + C(j, l) * dp[i][j][k]) % mod;
                for(int l=0; l<=i-j; l++) dp[i+1][j][k+j+l] = (dp[i+1][j][k+j+l] + C(i-j, l) * dp[i][j][k]) % mod;
            }
        }
    }

    ll ans = 0;
    for(int j=0; j<=n; j++) ans = (ans + dp[n][j][m]) % mod;
    ans -= C(C(n, 2), m);
    if(ans < 0) ans += mod;
    cout << ans << endl;
} 


int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    init();
    int t = 1;
    // cin >> t;
    while(t--)
    solve();
    return 0;
}

### 時間複雜度 ：$O(N^5)$
###### tags: `dp` `combinatorics` `graph`