C++ の動作確認をしてみた（２４９）

C++の練習を兼ねて, AtCoder Beginner Contest 171 の問題F (Strivore) を解いてみた.

■感想.
1. 解答方針が全く見えなかったので, 解説を見て実装したところ, AC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// C++ (GCC 9.2.1)
// 解き直し.
// https://img.atcoder.jp/abc171/editorial.pdf
#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 = 2020202;
LL FAC[LIMIT], INV[LIMIT], C[LIMIT], mPow25[LIMIT], mPow26[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 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 K;
    char c[1010101];
    scanf("%d %s", &K, c);
    int N = strlen(c);
    FAC[0] = 1, mPow25[0] = 1, mPow26[0] = 1;
    repx(i, 1, LIMIT){
        FAC[i] = (LL)i * FAC[i - 1] % MOD;
        mPow25[i] = mPow25[i - 1] * 25LL % MOD;
        mPow26[i] = mPow26[i - 1] * 26LL % MOD;
    }
    rep(i, LIMIT) INV[i] = mPow(FAC[i], MOD - 2);
    
    // 2. S[N] の 位置ごとに集計(解説通り).
    LL ans = 0;
    repx(i, N - 1, N + K){
        // 2-1. S[1] ～ S[N - 1] の 選び方.
        LL a = combination((LL)i, (LL)(N - 1));
        
        // 2-2. S[i]以外の文字の選び方.
        int cnt = (N + K - 1) - i; // S[N]以降の文字数.
        LL b = mPow25[K - cnt] * mPow26[cnt] % MOD;
        
        // 2-3. 集計.
        ans = (ans + a * b) % MOD;
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++ (GCC 9.2.1)

// 解き直し.

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

#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 = 2020202;

LL FAC[LIMIT], INV[LIMIT], C[LIMIT], mPow25[LIMIT], mPow26[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 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 K;

char c[1010101];

scanf("%d %s", &K, c);

int N = strlen(c);

FAC[0] = 1, mPow25[0] = 1, mPow26[0] = 1;

repx(i, 1, LIMIT){

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

mPow25[i] = mPow25[i - 1] * 25LL % MOD;

mPow26[i] = mPow26[i - 1] * 26LL % MOD;

}

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

// 2. S[N] の位置ごとに集計(解説通り).

LL ans = 0;

repx(i, N - 1, N + K){

// 2-1. S[1] ～ S[N - 1] の選び方.

LL a = combination((LL)i, (LL)(N - 1));

// 2-2. S[i]以外の文字の選び方.

int cnt = (N + K - 1) - i; // S[N]以降の文字数.

LL b = mPow25[K - cnt] * mPow26[cnt] % MOD;

// 2-3. 集計.

ans = (ans + a * b) % MOD;

}

// 3. 出力.

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

return 0;

}

[入力例]
5
oof

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

[入力例]
37564
whydidyoudesertme

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

[入力例]
314159
atcoderonehundredandseventyfirsttaskf

[出力例]
791705302

[入力例]

oof

[出力例]

575111451

※AtCoderテストケースより

[入力例]

37564

whydidyoudesertme

[出力例]

318008117

※AtCoderテストケースより

[入力例]

314159

atcoderonehundredandseventyfirsttaskf

[出力例]

791705302

■参照サイト
AtCoder Beginner Contest 171

C++の練習を兼ねて, AtCoder Beginner Contest 171 の 問題F (Strivore) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 171 の問題F (Strivore) を解いてみた.

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