C++ の動作確認をしてみた（６５５）

C++の練習を兼ねて, AtCoder Beginner Contest 127 の問題E (Cell Distance) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説にある通り, X, Y方向で, 独立に数え上げできるという部分が, 面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 127 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/abc127/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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--)
const LL MOD = 1e9 + 7;
const int LIMIT = 202020;
LL FAC[LIMIT], 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 0LL;
    if(n == k || k == 0LL) return 1LL;
    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);
    
    // 2. 事前計算.
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, LIMIT)     INV[i] = mPow(FAC[i], MOD - 2);
    
    // 3. 各座標ごとの差の絶対値の和.
    // -> 2マスを, 固定で選んだ場合の数, 差の絶対値 d を 乗ずることを忘れないこと!
    // 3-1. X方向.
    LL x = 0;
    repx(d, 1, N){
        x += (LL)(N - d) * (LL)M % MOD * (LL)M % MOD * (LL)d % MOD;
        x %= MOD;
    }
    
    // 3-2. Y方向.
    LL y = 0;
    repx(d, 1, M){
        y += (LL)(M - d) * (LL)N % MOD * (LL)N % MOD * (LL)d % MOD;
        y %= MOD;
    }
    
    // 4. (K - 2)マス選ぶ場合の数.
    // -> 固定で選んだ 2マス以外のマスの選び方(解説より).
    LL k2 = combination((LL)(N * M - 2), (LL)(K - 2));
    
    // 5. 集計.
    // -> X, Y方向は, 独立と考えて良いとのこと(解説より).
    LL ans = (x + y) % MOD * k2 % MOD;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/abc127/editorial.pdf

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#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--)

const LL MOD = 1e9 + 7;

const int LIMIT = 202020;

LL FAC[LIMIT], 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 0LL;

if(n == k || k == 0LL) return 1LL;

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);

// 2. 事前計算.

FAC[0] = 1;

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

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

// 3. 各座標ごとの差の絶対値の和.

// -> 2マスを, 固定で選んだ場合の数, 差の絶対値 d を乗ずることを忘れないこと!

// 3-1. X方向.

LL x = 0;

repx(d, 1, N){

x += (LL)(N - d) * (LL)M % MOD * (LL)M % MOD * (LL)d % MOD;

x %= MOD;

}

// 3-2. Y方向.

LL y = 0;

repx(d, 1, M){

y += (LL)(M - d) * (LL)N % MOD * (LL)N % MOD * (LL)d % MOD;

y %= MOD;

}

// 4. (K - 2)マス選ぶ場合の数.

// -> 固定で選んだ 2マス以外のマスの選び方(解説より).

LL k2 = combination((LL)(N * M - 2), (LL)(K - 2));

// 5. 集計.

// -> X, Y方向は, 独立と考えて良いとのこと(解説より).

LL ans = (x + y) % MOD * k2 % MOD;

// 6. 出力.

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

return 0;

}

[入力例]
2 2 2

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

[入力例]
4 5 4

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

[入力例]
100 100 5000

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

[入力例]
3 4 5

[出力例]
18480

[入力例]
7 8 3

[出力例]
415800

[入力例]
202 203 12345

[出力例]
906503729

[入力例]

2 2 2

[出力例]

※AtCoderテストケースより

[入力例]

4 5 4

[出力例]

87210

※AtCoderテストケースより

[入力例]

100 100 5000

[出力例]

817260251

※AtCoderテストケースより

[入力例]

3 4 5

[出力例]

18480

[入力例]

7 8 3

[出力例]

415800

[入力例]

202 203 12345

[出力例]

906503729

■参照サイト
AtCoder Beginner Contest 127

C++の練習を兼ねて, AtCoder Beginner Contest 127 の 問題E (Cell Distance) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 127 の問題E (Cell Distance) を解いてみた.

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