C++ の動作確認をしてみた（１３２）

C++の練習を兼ねて, AtCoder Beginner Contest 145 の問題D (D – Knight) を解いてみた.

■感想.
1. 解説見る前に, AC版となったので良かったと思う.
2. 解説と同様の方針で解答出来たので, 及第点は取れたと思う.

本家のサイトABC 145解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define repx(i, a, b) for(int i = a; i < b; i++)
using LL = long long;
const LL MOD = 1e9 + 7;
const int LIMIT = 1e6 + 1;
LL FAC[LIMIT + 1];
LL INV[LIMIT + 1];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL inverse(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)の計算結果.
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. 入力情報.
    LL X, Y;
    scanf("%lld %lld", &X, &Y);
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, LIMIT)     INV[i] = inverse(FAC[i], MOD - 2) % MOD;
    
    // 2. ナイトの駒を移動.
    // 移動方法は, (1, 2) または (2, 1) を 選択できるので, それぞれの操作回数を計算.
    // X = 1 * op12 + 2 * op21, Y = 2 * op12 + 1 * op21
    // -> 
    // 1 * op12 = X - 2 * op21
    // 2 * op12 = Y - 1 * op21
    // -> 
    // op12 = (2 * Y - X) / 3
    // op21 = (2 * X - Y) / 3
    LL op12 = (2 * Y - X) / 3, op21 = (2 * X - Y) / 3;
    
    // 3. 移動できない場合.
    if(X != op12 + 2 * op21 || Y != 2 * op12 + op21){
        printf("%d\n", 0);
        return 0;
    }
    
    // 4. 移動させる方法が何通りあるか？
    LL ans = combination(op12 + op21, op12);
    
    // 5. 出力 ～ 後処理.
    printf("%lld\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)

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

using LL = long long;

const LL MOD = 1e9 + 7;

const int LIMIT = 1e6 + 1;

LL FAC[LIMIT + 1];

LL INV[LIMIT + 1];

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

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

// @param b: 指数.

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

LL inverse(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)の計算結果.

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. 入力情報.

LL X, Y;

scanf("%lld %lld", &X, &Y);

FAC[0] = 1;

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

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

// 2. ナイトの駒を移動.

// 移動方法は, (1, 2) または (2, 1) を選択できるので, それぞれの操作回数を計算.

// X = 1 * op12 + 2 * op21, Y = 2 * op12 + 1 * op21

// ->

// 1 * op12 = X - 2 * op21

// 2 * op12 = Y - 1 * op21

// ->

// op12 = (2 * Y - X) / 3

// op21 = (2 * X - Y) / 3

LL op12 = (2 * Y - X) / 3, op21 = (2 * X - Y) / 3;

// 3. 移動できない場合.

if(X != op12 + 2 * op21 || Y != 2 * op12 + op21){

printf("%d\n", 0);

return 0;

}

// 4. 移動させる方法が何通りあるか？

LL ans = combination(op12 + op21, op12);

// 5. 出力～後処理.

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

return 0;

}

[入力例]
3 3

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

[入力例]
2 2

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

[入力例]
999999 999999

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

[入力例]
1000000 1000000

[出力例]
0

[入力例]
332211 223311

[出力例]
170944920

[入力例]
987654 876543

[出力例]
76408594

[入力例]

3 3

[出力例]

※AtCoderテストケースより

[入力例]

2 2

[出力例]

※AtCoderテストケースより

[入力例]

999999 999999

[出力例]

151840682

※AtCoderテストケースより

[入力例]

1000000 1000000

[出力例]

[入力例]

332211 223311

[出力例]

170944920

[入力例]

987654 876543

[出力例]

76408594

■参照サイト
AtCoder Beginner Contest 145

C++の練習を兼ねて, AtCoder Beginner Contest 145 の 問題D (D – Knight) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 145 の問題D (D – Knight) を解いてみた.

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