C++ の動作確認をしてみた（７７８）

C++の練習を兼ねて, AtCoder Beginner Contest 262 の問題E (Red and Blue Graph) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 解説の方針で, 数え上げできることが, 非常に印象的と思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc262/editorial/4479
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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 pb push_back
const LL MOD = 998244353;
const int LIMIT = 202020;
LL FAC[LIMIT];
LL INV[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;
}

// 組み合わせ(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, K;
    scanf("%d %d %d", &N, &M, &K);
    vvi G(N);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        --a, --b;
        G[a].pb(b);
        G[b].pb(a);
    }
    
    // 2. 事前準備.
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = i * FAC[i - 1] % MOD;
    rep(i, LIMIT)     INV[i] = mPow(FAC[i], MOD - 2) % MOD;
    
    // 3. 次数.
    LL e = 0, o = 0;
    rep(i, N){
        if(G[i].size() & 1) ++o;
        else                ++e;
    }
    
    // 4. 集計.
    LL ans = 0;
    rep(i, K / 2 + 1){
        int r = 2 * i;
        if(K - r < 0) break;
        ans += combination(o, r) * combination(e, K - r);
        ans %= MOD;
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc262/editorial/4479

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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 pb push_back

const LL MOD = 998244353;

const int LIMIT = 202020;

LL FAC[LIMIT];

LL INV[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;

}

// 組み合わせ(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, K;

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

vvi G(N);

rep(i, M){

int a, b;

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

--a, --b;

G[a].pb(b);

G[b].pb(a);

}

// 2. 事前準備.

FAC[0] = 1;

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

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

// 3. 次数.

LL e = 0, o = 0;

rep(i, N){

if(G[i].size() & 1) ++o;

else ++e;

}

// 4. 集計.

LL ans = 0;

rep(i, K / 2 + 1){

int r = 2 * i;

if(K - r < 0) break;

ans += combination(o, r) * combination(e, K - r);

ans %= MOD;

}

// 5. 出力.

printf("%lld\n", ans);

return 0;

}

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

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

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

[出力例]
64
※AtCoderテストケースより

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

[出力例]
56

[入力例]
15 18 6
1 2
1 3
3 2
15 2
15 14
14 13
4 5
4 6
5 6
5 7
7 6
8 9
9 12
8 10
8 12
11 9
11 10
11 12

[出力例]
2485

[入力例]
19 22 8
1 2
1 3
2 4
4 3
10 2
10 11
11 12
12 15
15 14
13 14
10 13
15 7
7 9
8 9
8 5
6 5
7 6
18 5
19 17
18 17
19 18
19 3

[出力例]
37742

100

[入力例]

4 4 2

1 2

1 3

2 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

10 10 3

1 2

2 4

1 5

3 6

3 9

4 10

7 8

9 10

5 9

3 4

[出力例]

※AtCoderテストケースより

[入力例]

10 15 3

1 9

1 10

1 2

1 3

1 4

2 3

2 4

3 4

4 5

4 6

4 7

4 8

5 8

6 7

7 8

[出力例]

[入力例]

15 18 6

1 2

1 3

3 2

15 2

15 14

14 13

4 5

4 6

5 6

5 7

7 6

8 9

9 12

8 10

8 12

11 9

11 10

11 12

[出力例]

2485

[入力例]

19 22 8

1 2

1 3

2 4

4 3

10 2

10 11

11 12

12 15

15 14

13 14

10 13

15 7

7 9

8 9

8 5

6 5

7 6

18 5

19 17

18 17

19 18

19 3

[出力例]

37742

■参照サイト
第三回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 262）

C++の練習を兼ねて, AtCoder Beginner Contest 262 の 問題E (Red and Blue Graph) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 262 の問題E (Red and Blue Graph) を解いてみた.

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