BestCoder Round #25 解題報告：有向圖環檢測與 DP 計數

題目 A：有向圖環檢測

判斷有向圖中是否存在環。數據範圍小 (N ≤ 200)，可用暴力 DFS：對每條邊 u→v，從 v 出發 DFS 看能否回到 u。若能，說明存在環。

// 核心 DFS
bool dfs(int x, int target) {
    if (x == target) return true;
    if (vis[x]) return false;
    vis[x] = true;
    for (int y : g[x]) if (dfs(y, target)) return true;
    return false;
}

// 主循環：枚舉每條邊 u->v，從 v 找 u
for (int u = 1; u <= n; ++u)
    for (int v : g[u]) {
        memset(vis, 0, sizeof(vis));
        if (dfs(v, u)) { hasCycle = true; break; }
    }

題目 B：網格放寶石 DP

N 行 M 列網格，每行至少放一顆寶石，求方案數。定義 dp[i][j]：前 i 行，恰有 j 列放了寶石的方案數。轉移枚舉第 i+1 行放 k 顆，其中 t 顆放在無寶石列：

dp[i+1][j+t] += dp[i][j] * C[M-j][t] * C[j][k-t]

預處理組合數 C[n][k] 模 1e9+7。最終答案 dp[N][M]。

// 核心 DP
for (int i = 1; i <= N; ++i)
    for (int j = 0; j <= M; ++j) if (dp[i][j])
        for (int k = 1; k <= M; ++k) // 第 i 行放 k 顆
            for (int t = 0; t <= min(k, M-j); ++t) {
                if (k-t > j) continue;
                dp[i+1][j+t] = (dp[i+1][j+t] + dp[i][j] * C[M-j][t] % MOD * C[j][k-t]) % MOD;
            }

心得總結

• A 題：小數據範圍下暴力 DFS 往往比複雜算法（拓撲/強連通）更快寫、更不易錯
• B 題：狀態壓縮為「已覆蓋列數」，轉移時分類討論新增列與舊列的選擇組合
• 組合數預處理 + DP 是計數類問題的標準套路