C++ の動作確認をしてみた（４３０）

C++の練習を兼ねて, AtCoder Regular Contest 115 の問題D (Odd Degree) を解いてみた.

■感想.
1. 問題Dは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 苦手なdpの訓練を積めたので, 非常に良かったと思う.
3. 幅優先探索の復習が出来たので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイト AtCoder Regular Contest 115 解説の各リンクをご覧下さい.

■C++版プログラム(問題D／AC版).

// 解き直し.
// https://atcoder.jp/contests/arc115/editorial/853
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
#define pb push_back
const LL MOD = 998244353;
const int LIMIT = 5050;
LL FAC[LIMIT], INV[LIMIT], g[LIMIT][LIMIT], dp[LIMIT][LIMIT];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return: べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t % MOD;
}

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    vector<P> edges;
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--;
        b--;
        G[a].pb(b);
        G[b].pb(a);
        edges.pb({a, b});
    }
    FAC[0] = 1;
    repx(i, 1, N + 1) FAC[i] = i * FAC[i - 1] % MOD;
    rep(i, N + 1)     INV[i] = mPow(FAC[i], MOD - 2) % MOD;
    
    // 2. グラフを連結成分に分解.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 2-1. 空のキュー.
        queue<int> q;
        
        // 2-2. 連結成分番号を設定.
        c[s] = l;
        
        // 2-3. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 2-4. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 2-5. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 2-6. 訪問済であれば, 処理をスキップ.
                if(c[e])            continue;
                if(!c[e] && e != s) c[e] = l, q.push(e);
            }
        }
        return;
    };
    int c[N], idx = 0;
    rep(i, N) c[i] = 0;
    rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);
    // rep(i, N) printf("%d ", c[i]);
    // puts("");
    
    // 3. 連結成分ごとの頂点数, 辺数 を 計算.
    set<int> gn[idx]; // 各連結成分に対する頂点.
    int gm[idx];      // 各連結成分に対する辺数.
    rep(i, idx) gm[i] = 0;
    for(auto &e : edges){
        int a, b;
        a = e.a;
        b = e.b;
        int n = c[a] - 1;
        assert(c[a] == c[b]);
        
        // 頂点を保存.
        gn[n].insert(a);
        gn[n].insert(b);
        
        // 辺数をカウント.
        gm[n]++;
    }
    
    // 4. 連結成分ごとに集計.
    rep(i, idx){
        LL m = (LL)gm[i];
        LL n = (LL)gn[i].size();
        LL o = m - n + 1LL;
        rep(k, N + 1){
            // K が 奇数.
            // - >何もしない
            if(k & 1) continue;
            
            // K が 偶数.
            // -> 辺が有る場合は, 全域木を適当に一つ取り, 全域木に含まれない辺を残すかどうか自由に決める.
            LL res = (m == 0) ? 1LL : mPow(2LL, o);
            g[i][k] = res * combination(n, (LL)k) % MOD;
        }
    }
    
    // 5. dp更新.
    int nSum = gn[0].size();
    rep(k, nSum + 1) dp[0][k] = g[0][k];
    repx(i, 1, idx){
        // 5-1. 頂点数設定.
        int nCur = gn[i].size();
        
        // 5-2. (i - 1)番目の状態をベースに, i番目の状態を決定.
        rep(k1, nSum + 1){
            rep(k2, nCur + 1){
                dp[i][k1 + k2] += dp[i - 1][k1] * g[i][k2];
                dp[i][k1 + k2] %= MOD;
            }
        }
        
        // 5-3. 頂点数合計を更新.
        nSum += nCur;
    }
    
    // 6. 出力.
    rep(i, N + 1) printf("%lld\n", dp[idx - 1][i]);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

// 解き直し.

// https://atcoder.jp/contests/arc115/editorial/853

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

using vi = vector<int>;

using vvi = vector<vi>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define a first

#define b second

#define pb push_back

const LL MOD = 998244353;

const int LIMIT = 5050;

LL FAC[LIMIT], INV[LIMIT], g[LIMIT][LIMIT], dp[LIMIT][LIMIT];

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t % MOD;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int N, M;

scanf("%d %d", &N, &M);

vvi G(N);

vector<P> edges;

rep(i, M){

int a, b;

scanf("%d %d", &a, &b);

a--;

b--;

G[a].pb(b);

G[b].pb(a);

edges.pb({a, b});

}

FAC[0] = 1;

repx(i, 1, N + 1) FAC[i] = i * FAC[i - 1] % MOD;

rep(i, N + 1) INV[i] = mPow(FAC[i], MOD - 2) % MOD;

// 2. グラフを連結成分に分解.

// https://ja.wikipedia.org/wiki/幅優先探索

auto bfs = [&](vvi &G, int s, int* c, int l){

// 2-1. 空のキュー.

queue<int> q;

// 2-2. 連結成分番号を設定.

c[s] = l;

// 2-3. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// 2-4. キューから取り出す.

int u = q.front();

q.pop();

// 2-5. 取り出した要素を処理.

for(auto &e : G[u]){

// 2-6. 訪問済であれば, 処理をスキップ.

if(c[e]) continue;

if(!c[e] && e != s) c[e] = l, q.push(e);

}

return;

};

int c[N], idx = 0;

rep(i, N) c[i] = 0;

rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);

// rep(i, N) printf("%d ", c[i]);

// puts("");

// 3. 連結成分ごとの頂点数, 辺数を計算.

set<int> gn[idx]; // 各連結成分に対する頂点.

int gm[idx]; // 各連結成分に対する辺数.

rep(i, idx) gm[i] = 0;

for(auto &e : edges){

int a, b;

a = e.a;

b = e.b;

int n = c[a] - 1;

assert(c[a] == c[b]);

// 頂点を保存.

gn[n].insert(a);

gn[n].insert(b);

// 辺数をカウント.

gm[n]++;

}

// 4. 連結成分ごとに集計.

rep(i, idx){

LL m = (LL)gm[i];

LL n = (LL)gn[i].size();

LL o = m - n + 1LL;

rep(k, N + 1){

// K が奇数.

// - >何もしない

if(k & 1) continue;

// K が偶数.

// -> 辺が有る場合は, 全域木を適当に一つ取り, 全域木に含まれない辺を残すかどうか自由に決める.

LL res = (m == 0) ? 1LL : mPow(2LL, o);

g[i][k] = res * combination(n, (LL)k) % MOD;

}

// 5. dp更新.

int nSum = gn[0].size();

rep(k, nSum + 1) dp[0][k] = g[0][k];

repx(i, 1, idx){

// 5-1. 頂点数設定.

int nCur = gn[i].size();

// 5-2. (i - 1)番目の状態をベースに, i番目の状態を決定.

rep(k1, nSum + 1){

rep(k2, nCur + 1){

dp[i][k1 + k2] += dp[i - 1][k1] * g[i][k2];

dp[i][k1 + k2] %= MOD;

}

// 5-3. 頂点数合計を更新.

nSum += nCur;

}

// 6. 出力.

rep(i, N + 1) printf("%lld\n", dp[idx - 1][i]);

return 0;

}

[入力例]
3 2
1 2
2 3

[出力例]
1
0
3
0
※AtCoderのテストケースより

[入力例]
4 2
1 2
3 4

[出力例]
1
0
2
0
1
※AtCoderのテストケースより

[入力例]
5 4
1 2
3 2
1 3
4 5

[出力例]
2
0
8
0
6
0

[入力例]
7 8
1 2
2 3
3 4
4 1
3 1
5 6
6 7
7 5

[出力例]
8
0
72
0
152
0
24
0

[入力例]
10 15
1 2
1 3
2 3
1 4
1 5
6 7
6 8
6 9
6 10
7 8
7 9
7 10
8 9
8 10
9 10

[出力例]
128
0
2560
0
14080
0
12800
0
3200
0
0

[入力例]

3 2

1 2

2 3

[出力例]

※AtCoderのテストケースより

[入力例]

4 2

1 2

3 4

[出力例]

※AtCoderのテストケースより

[入力例]

5 4

1 2

3 2

1 3

4 5

[出力例]

[入力例]

7 8

1 2

2 3

3 4

4 1

3 1

5 6

6 7

7 5

[出力例]

152

[入力例]

10 15

1 2

1 3

2 3

1 4

1 5

6 7

6 8

6 9

6 10

7 8

7 9

7 10

8 9

8 10

9 10

[出力例]

128

2560

14080

12800

3200

■参照サイト
AtCoder Regular Contest 115

C++の練習を兼ねて, AtCoder Regular Contest 115 の 問題D (Odd Degree) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Regular Contest 115 の問題D (Odd Degree) を解いてみた.

コメントを残すコメントをキャンセル