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

C++の練習を兼ねて, AtCoder Beginner Contest 129 の問題F (F – Takahashi’s Basics in Education and Learning) を解いてみた.

■感想.
1. 解答の方針が, 全く見えなかったので, 解説を読んだうえで, 実装した.
2. 但し, 実装上, 部分的に, いくつも推測(ex. Cd乗の解釈など)しているため, 題意と, ズレている可能性があると思われる.
3. あと, 実装後, テストケース(sub1_killer_04.txt)で, 必ず弾かれてしまうので, ネット上で調べたところ, atcoder_testcases ABC129で, テストケースが公開されていることが分かったので, 内容を確認したところ, 計算範囲が, 小さいことによるバグと判明した.
4. 再提出したところ, ようやく AC版となった, 計算範囲の把握が大事であることが分かったので, 今後も役立つと思った.

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

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

// 解き直し.
// ABC 129解説.
// https://img.atcoder.jp/abc129/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL m[9];

// 行列積のロジックを一部抽出した版.
// @param p1 ～ q3: 行列の要素.
// @param MOD: M.
// @return ret: 行列積の計算結果.
LL matrixProduct(LL p1, LL p2, LL p3, LL q1, LL q2, LL q3, LL MOD){
    LL ret = 0;
    ret += (p1 % MOD) * (q1 % MOD), ret %= MOD;
    ret += (p2 % MOD) * (q2 % MOD), ret %= MOD;
    ret += (p3 % MOD) * (q3 % MOD), ret %= MOD;
    return ret;
}

// 本問で設定している (3×3)行列 の Cd 乗 を 計算.
// @param p: Cd乗.
// @param a: 10 の d乗.
// @param b: B.
// @param MOD: M.
// @return: 特に無し.
void matrix33(LL p, LL a, LL b, LL MOD){

    // 1. p を 2 で 割っていく(q: 商, r: 余り).
    map<LL, LL> t;
    while(p){
        LL q = p >> 1, r = p & 1;
        t[q] = r;
        p >>= 1;
    }
    // for(auto &p : t) cout << p.first << " " << p.second << endl;

    // 2. 1. の 結果から, 逆算.
    // (初期状態)
    // 第 0成分(1行1列): a, 第 1成分(1行2列): 0, 第 2成分(1行3列): 0
    // 第 3成分(2行1列): 1, 第 4成分(2行2列): 1, 第 5成分(2行3列): 0
    // 第 6成分(3行1列): 0, 第 7成分(3行2列): b, 第 8成分(3行3列): 1
    m[0] = 1, m[1] = 0, m[2] = 0;
    m[3] = 0, m[4] = 1, m[5] = 0;
    m[6] = 0, m[7] = 0, m[8] = 1;
    for(auto &p : t){
        if(p.first != 0){
            LL t11 = m[0], t12 = m[1], t13 = m[2],
               t21 = m[3], t22 = m[4], t23 = m[5],
               t31 = m[6], t32 = m[7], t33 = m[8];
            m[0] = matrixProduct(t11, t12, t13, t11, t21, t31, MOD);
            m[1] = matrixProduct(t11, t12, t13, t12, t22, t32, MOD);
            m[2] = matrixProduct(t11, t12, t13, t13, t23, t33, MOD);
            m[3] = matrixProduct(t21, t22, t23, t11, t21, t31, MOD);
            m[4] = matrixProduct(t21, t22, t23, t12, t22, t32, MOD);
            m[5] = matrixProduct(t21, t22, t23, t13, t23, t33, MOD);
            m[6] = matrixProduct(t31, t32, t33, t11, t21, t31, MOD);
            m[7] = matrixProduct(t31, t32, t33, t12, t22, t32, MOD);
            m[8] = matrixProduct(t31, t32, t33, t13, t23, t33, MOD);
        }
        if(p.second == 1){
            LL t11 = m[0], t12 = m[1], t13 = m[2],
               t21 = m[3], t22 = m[4], t23 = m[5],
               t31 = m[6], t32 = m[7], t33 = m[8];
            m[0] = matrixProduct(t11, t12, t13, a, 1, 0, MOD);
            m[1] = matrixProduct(t11, t12, t13, 0, 1, b, MOD);
            m[2] = matrixProduct(t11, t12, t13, 0, 0, 1, MOD);
            m[3] = matrixProduct(t21, t22, t23, a, 1, 0, MOD);
            m[4] = matrixProduct(t21, t22, t23, 0, 1, b, MOD);
            m[5] = matrixProduct(t21, t22, t23, 0, 0, 1, MOD);
            m[6] = matrixProduct(t31, t32, t33, a, 1, 0, MOD);
            m[7] = matrixProduct(t31, t32, t33, 0, 1, b, MOD);
            m[8] = matrixProduct(t31, t32, t33, 0, 0, 1, MOD);
        }
    }
    
    return;

}

int main() {
    
    // 1. 入力情報取得.
    LL L, A, B, M;
    scanf("%lld %lld %lld %lld", &L, &A, &B, &M);
    
    // 2. 解説通り.
    // d = 1, 2, ... , 18 で, 解説にある, 以下の計算式をベースに合算.
    // [計算式]
    // (X, s, 1) × matrix33(Cd, 10 の d乗, B, M) = (X × 10 の d乗 + s, s + B, 1)
    LL ans[3] = {0, A, 1};
    LL cur10 = 1, bef10 = 1;
    // 以下のテストケースが, 正しく通らなかった.
    // sub1_killer_04.txt
    // https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAGk5qU1izrmUvpKMvgSN7ga/ABC129/F/in?dl=0&preview=sub1_killer_04.txt&subfolder_nav_tracking=1
    // [入力例]
    // 1 999999999999999999 999999999999999999 998244353
    // 
    // [出力例]
    // 716070897 が 正解らしいが, 0 と 出力されてしまう.
    // -> 計算範囲が足りてないことが分かったので, for文 の 範囲 を 修正.
    // for(int i = 1; i <= 18; i++){
    for(int i = 1; i < 20; i++){
        // 2-1. 10 の べき乗 を 更新.
        cur10 *= 10;

        // 2-2. Cd を 計算.
        // i を 数列の桁数 と 見て, 計算.
        // ex.
        // i = 1, A = 3, B = 4 の 場合.
        // 0桁 … max(0, 0 - A) ÷ B = 0
        // 1桁 … max(0, 9 - A) ÷ B = 1
        // -> C1 = 1 - 0 = 1個.
        // ※ C1 は 2個 の はず.
        // 
        // i = 2, A = 3, B = 4 の 場合.
        // 1桁 … max(0, 9 - A)  ÷ B =  1
        // 2桁 … max(0, 99 - A) ÷ B = 24
        // -> C2 = 24 - 1 = 23個.
        // 
        // i = 3, A = 3, B = 4 の 場合.
        // 2桁 … max(0, 99 - A)  ÷ B =  24
        // 3桁 … max(0, 999 - A) ÷ B = 249
        // -> C3 = 249 - 24 = 225個.
        LL d1 = max(0LL, bef10 - 1 - A) / B;
        LL d2 = max(0LL, cur10 - 1 - A) / B;
        LL Cd = d2 - d1;
        // d1 が 0 の場合 かつ d2 が 0 より大きい場合は, 
        // d2 の方で, 初項 A を 含んでいる筈なので, Cd を 1増やす必要があるはず.
        if(d1 == 0 && d2 > 0) Cd++;
        // printf("Cd=%lld, L=%lld\n", Cd, L);
        // printf("cur10=%lld, bef10=%lld\n", cur10, bef10);

        // 2-3. 行列計算.
        matrix33(min(Cd, L), cur10, B, M);
        
        // 2-4. 行列 ans を 更新.
        LL t[3] = {0, 0, 0};
        t[0] = matrixProduct(ans[0], ans[1], ans[2], m[0], m[3], m[6], M);
        t[1] = matrixProduct(ans[0], ans[1], ans[2], m[1], m[4], m[7], M);
        t[2] = matrixProduct(ans[0], ans[1], ans[2], m[2], m[5], m[8], M);
        swap(t, ans);
        
        // 2-5. 計算を継続するかチェック.
        // 等差数列の長さは, L と指定されているので, 1回計算するごとに, Cd個分 を 減らす 必要あり.
        L -= Cd;
        // L が 0以下となったら, 計算終了と見ることが出来る.
        if(L <= 0) break;
        
        // 2-6. 前回 の 10 の べき乗 を 保存.
        bef10 = cur10;
    }
    
    // for(int i = 0; i < 3; i++) printf("ans[%d]=%lld ", i, ans[i]);
    // printf("\n");
    
    // 3. 出力 ～ 後処理.
    printf("%lld\n", ans[0]);
    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

157

158

159

160

161

// 解き直し.

// ABC 129解説.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

LL m[9];

// 行列積のロジックを一部抽出した版.

// @param p1 ～ q3: 行列の要素.

// @param MOD: M.

// @return ret: 行列積の計算結果.

LL matrixProduct(LL p1, LL p2, LL p3, LL q1, LL q2, LL q3, LL MOD){

LL ret = 0;

ret += (p1 % MOD) * (q1 % MOD), ret %= MOD;

ret += (p2 % MOD) * (q2 % MOD), ret %= MOD;

ret += (p3 % MOD) * (q3 % MOD), ret %= MOD;

return ret;

}

// 本問で設定している (3×3)行列の Cd 乗を計算.

// @param p: Cd乗.

// @param a: 10 の d乗.

// @param b: B.

// @param MOD: M.

// @return: 特に無し.

void matrix33(LL p, LL a, LL b, LL MOD){

// 1. p を 2 で割っていく(q: 商, r: 余り).

map<LL, LL> t;

while(p){

LL q = p >> 1, r = p & 1;

t[q] = r;

p >>= 1;

}

// for(auto &p : t) cout << p.first << " " << p.second << endl;

// 2. 1. の結果から, 逆算.

// (初期状態)

// 第 0成分(1行1列): a, 第 1成分(1行2列): 0, 第 2成分(1行3列): 0

// 第 3成分(2行1列): 1, 第 4成分(2行2列): 1, 第 5成分(2行3列): 0

// 第 6成分(3行1列): 0, 第 7成分(3行2列): b, 第 8成分(3行3列): 1

m[0] = 1, m[1] = 0, m[2] = 0;

m[3] = 0, m[4] = 1, m[5] = 0;

m[6] = 0, m[7] = 0, m[8] = 1;

for(auto &p : t){

if(p.first != 0){

LL t11 = m[0], t12 = m[1], t13 = m[2],

t21 = m[3], t22 = m[4], t23 = m[5],

t31 = m[6], t32 = m[7], t33 = m[8];

m[0] = matrixProduct(t11, t12, t13, t11, t21, t31, MOD);

m[1] = matrixProduct(t11, t12, t13, t12, t22, t32, MOD);

m[2] = matrixProduct(t11, t12, t13, t13, t23, t33, MOD);

m[3] = matrixProduct(t21, t22, t23, t11, t21, t31, MOD);

m[4] = matrixProduct(t21, t22, t23, t12, t22, t32, MOD);

m[5] = matrixProduct(t21, t22, t23, t13, t23, t33, MOD);

m[6] = matrixProduct(t31, t32, t33, t11, t21, t31, MOD);

m[7] = matrixProduct(t31, t32, t33, t12, t22, t32, MOD);

m[8] = matrixProduct(t31, t32, t33, t13, t23, t33, MOD);

}

if(p.second == 1){

LL t11 = m[0], t12 = m[1], t13 = m[2],

t21 = m[3], t22 = m[4], t23 = m[5],

t31 = m[6], t32 = m[7], t33 = m[8];

m[0] = matrixProduct(t11, t12, t13, a, 1, 0, MOD);

m[1] = matrixProduct(t11, t12, t13, 0, 1, b, MOD);

m[2] = matrixProduct(t11, t12, t13, 0, 0, 1, MOD);

m[3] = matrixProduct(t21, t22, t23, a, 1, 0, MOD);

m[4] = matrixProduct(t21, t22, t23, 0, 1, b, MOD);

m[5] = matrixProduct(t21, t22, t23, 0, 0, 1, MOD);

m[6] = matrixProduct(t31, t32, t33, a, 1, 0, MOD);

m[7] = matrixProduct(t31, t32, t33, 0, 1, b, MOD);

m[8] = matrixProduct(t31, t32, t33, 0, 0, 1, MOD);

}

return;

}

int main() {

// 1. 入力情報取得.

LL L, A, B, M;

scanf("%lld %lld %lld %lld", &L, &A, &B, &M);

// 2. 解説通り.

// d = 1, 2, ... , 18 で, 解説にある, 以下の計算式をベースに合算.

// [計算式]

// (X, s, 1) × matrix33(Cd, 10 の d乗, B, M) = (X × 10 の d乗 + s, s + B, 1)

LL ans[3] = {0, A, 1};

LL cur10 = 1, bef10 = 1;

// 以下のテストケースが, 正しく通らなかった.

// sub1_killer_04.txt

// https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAGk5qU1izrmUvpKMvgSN7ga/ABC129/F/in?dl=0&preview=sub1_killer_04.txt&subfolder_nav_tracking=1

// [入力例]

// 1 999999999999999999 999999999999999999 998244353

// [出力例]

// 716070897 が正解らしいが, 0 と出力されてしまう.

// -> 計算範囲が足りてないことが分かったので, for文の範囲を修正.

// for(int i = 1; i <= 18; i++){

for(int i = 1; i < 20; i++){

// 2-1. 10 のべき乗を更新.

cur10 *= 10;

// 2-2. Cd を計算.

// i を数列の桁数と見て, 計算.

// ex.

// i = 1, A = 3, B = 4 の場合.

// 0桁 … max(0, 0 - A) ÷ B = 0

// 1桁 … max(0, 9 - A) ÷ B = 1

// -> C1 = 1 - 0 = 1個.

// ※ C1 は 2個のはず.

// i = 2, A = 3, B = 4 の場合.

// 1桁 … max(0, 9 - A) ÷ B = 1

// 2桁 … max(0, 99 - A) ÷ B = 24

// -> C2 = 24 - 1 = 23個.

// i = 3, A = 3, B = 4 の場合.

// 2桁 … max(0, 99 - A) ÷ B = 24

// 3桁 … max(0, 999 - A) ÷ B = 249

// -> C3 = 249 - 24 = 225個.

LL d1 = max(0LL, bef10 - 1 - A) / B;

LL d2 = max(0LL, cur10 - 1 - A) / B;

LL Cd = d2 - d1;

// d1 が 0 の場合かつ d2 が 0 より大きい場合は,

// d2 の方で, 初項 A を含んでいる筈なので, Cd を 1増やす必要があるはず.

if(d1 == 0 && d2 > 0) Cd++;

// printf("Cd=%lld, L=%lld\n", Cd, L);

// printf("cur10=%lld, bef10=%lld\n", cur10, bef10);

// 2-3. 行列計算.

matrix33(min(Cd, L), cur10, B, M);

// 2-4. 行列 ans を更新.

LL t[3] = {0, 0, 0};

t[0] = matrixProduct(ans[0], ans[1], ans[2], m[0], m[3], m[6], M);

t[1] = matrixProduct(ans[0], ans[1], ans[2], m[1], m[4], m[7], M);

t[2] = matrixProduct(ans[0], ans[1], ans[2], m[2], m[5], m[8], M);

swap(t, ans);

// 2-5. 計算を継続するかチェック.

// 等差数列の長さは, L と指定されているので, 1回計算するごとに, Cd個分を減らす必要あり.

L -= Cd;

// L が 0以下となったら, 計算終了と見ることが出来る.

if(L <= 0) break;

// 2-6. 前回の 10 のべき乗を保存.

bef10 = cur10;

}

// for(int i = 0; i < 3; i++) printf("ans[%d]=%lld ", i, ans[i]);

// printf("\n");

// 3. 出力～後処理.

printf("%lld\n", ans[0]);

return 0;

}

[入力例]
5 3 4 10007

[出力例(debug版)]
Cd=2, L=5
Cd=23, L=3
ans[0]=5563 ans[1]=23 ans[2]=1 
5563
※AtCoderテストケースより

[入力例]
4 8 1 1000000

[出力例(debug版)]
Cd=2, L=4
Cd=90, L=2
ans[0]=891011 ans[1]=12 ans[2]=1 
891011
※AtCoderテストケースより

[入力例]
107 10000000000007 1000000000000007 998244353

[出力例(debug版)]
Cd=0, L=107
Cd=0, L=107
Cd=0, L=107
Cd=0, L=107
Cd=0, L=107
Cd=0, L=107
Cd=0, L=107
Cd=0, L=107
Cd=0, L=107
Cd=0, L=107
Cd=0, L=107
Cd=0, L=107
Cd=0, L=107
Cd=0, L=107
Cd=0, L=107
Cd=10, L=107
Cd=90, L=97
Cd=900, L=7
ans[0]=39122908 ans[1]=201747450 ans[2]=1 
39122908
※AtCoderテストケースより

[入力例(sub1_killer_04.txt)]
1 999999999999999999 999999999999999999 998244353

[出力例(debug版)]
Cd=0, L=1
Cd=0, L=1
Cd=0, L=1
Cd=0, L=1
Cd=0, L=1
Cd=0, L=1
Cd=0, L=1
Cd=0, L=1
Cd=0, L=1
Cd=0, L=1
Cd=0, L=1
Cd=0, L=1
Cd=0, L=1
Cd=0, L=1
Cd=0, L=1
Cd=0, L=1
Cd=0, L=1
Cd=0, L=1
Cd=10, L=1
ans[0]=716070897 ans[1]=433897441 ans[2]=1 
716070897
※AtCoderテストケースより

[入力例]
123 1234567654321 123456787654321 123454321

[出力例(debug版)]
Cd=0, L=123
Cd=0, L=123
Cd=0, L=123
Cd=0, L=123
Cd=0, L=123
Cd=0, L=123
Cd=0, L=123
Cd=0, L=123
Cd=0, L=123
Cd=0, L=123
Cd=0, L=123
Cd=0, L=123
Cd=0, L=123
Cd=0, L=123
Cd=9, L=123
Cd=72, L=114
Cd=729, L=42
ans[0]=24290706 ans[1]=95659107 ans[2]=1 
24290706

[入力例]
98765 12345654321 1234567654321 987654321

[出力例(debug版)]
Cd=0, L=98765
Cd=0, L=98765
Cd=0, L=98765
Cd=0, L=98765
Cd=0, L=98765
Cd=0, L=98765
Cd=0, L=98765
Cd=0, L=98765
Cd=0, L=98765
Cd=0, L=98765
Cd=0, L=98765
Cd=0, L=98765
Cd=9, L=98765
Cd=72, L=98756
Cd=729, L=98684
Cd=7290, L=97955
Cd=72901, L=90665
Cd=729000, L=17764
ans[0]=768437437 ans[1]=797217809 ans[2]=1 
768437437

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

[入力例]

5 3 4 10007

[出力例(debug版)]

Cd=2, L=5

Cd=23, L=3

ans[0]=5563 ans[1]=23 ans[2]=1

5563

※AtCoderテストケースより

[入力例]

4 8 1 1000000

[出力例(debug版)]

Cd=2, L=4

Cd=90, L=2

ans[0]=891011 ans[1]=12 ans[2]=1

891011

※AtCoderテストケースより

[入力例]

107 10000000000007 1000000000000007 998244353

[出力例(debug版)]

Cd=0, L=107

Cd=10, L=107

Cd=90, L=97

Cd=900, L=7

ans[0]=39122908 ans[1]=201747450 ans[2]=1

39122908

※AtCoderテストケースより

[入力例(sub1_killer_04.txt)]

1 999999999999999999 999999999999999999 998244353

[出力例(debug版)]

Cd=0, L=1

Cd=10, L=1

ans[0]=716070897 ans[1]=433897441 ans[2]=1

716070897

※AtCoderテストケースより

[入力例]

123 1234567654321 123456787654321 123454321

[出力例(debug版)]

Cd=0, L=123

Cd=9, L=123

Cd=72, L=114

Cd=729, L=42

ans[0]=24290706 ans[1]=95659107 ans[2]=1

24290706

[入力例]

98765 12345654321 1234567654321 987654321

[出力例(debug版)]

Cd=0, L=98765

Cd=9, L=98765

Cd=72, L=98756

Cd=729, L=98684

Cd=7290, L=97955

Cd=72901, L=90665

Cd=729000, L=17764

ans[0]=768437437 ans[1]=797217809 ans[2]=1

768437437

■参照サイト
AtCoder Beginner Contest 129
atcoder_testcases ABC129

C++の練習を兼ねて, AtCoder Beginner Contest 129 の 問題F (F – Takahashi’s Basics in Education and Learning) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 129 の問題F (F – Takahashi’s Basics in Education and Learning) を解いてみた.

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