結果

問題 No.260 世界のなんとか3
ユーザー alumina_8alumina_8
提出日時 2019-03-28 19:50:16
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,754 bytes
コンパイル時間 1,677 ms
コンパイル使用メモリ 105,364 KB
実行使用メモリ 32,608 KB
最終ジャッジ日時 2023-08-20 12:08:03
合計ジャッジ時間 5,845 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 40 ms
32,400 KB
testcase_01 AC 40 ms
32,452 KB
testcase_02 AC 40 ms
32,360 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 RE -
testcase_27 AC 40 ms
32,380 KB
testcase_28 RE -
testcase_29 AC 143 ms
32,468 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <numeric>
#include <array>
#include <cmath>
#include <memory>
using namespace std;
//変数デバッグ
#define DEB(variable) cout << #variable << '=' << variable << endl

//for簡易表記(引数ミス防止)
#define FOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin); (LoopVariable) < (numberOFend); (LoopVariable)++)
#define DEFOR(LoopVariable,numberOFbegin,numberOFend) for (int LoopVariable = (numberOFbegin)-1; (LoopVariable) >= (numberOFend); (LoopVariable)--)
#define REP(LoopVariable,numberOFend) for(int LoopVariable = 0;(LoopVariable)<(numberOFend);LoopVariable++)

constexpr long long int linf = numeric_limits<long long int>::max()-5;
constexpr int inf= numeric_limits<int>::max()-5;
constexpr long long int mod = 1000000007;



int main(){
    string s, t;
    cin >> s >> t;

    const int sn = (int)s.size(), tn = (int)t.size();
    int tmp = sn - 1;
    while(s[tmp]=='0'){
        s[tmp] = '9';
        tmp--;
    }
    s[tmp]--;

    vector<vector<vector<vector<vector<long long int>>>>> dp1(10001,vector<vector<vector<vector<long long int>>>>(2,vector<vector<vector<long long int>>>(2,vector<vector<long long int>>(3,vector<long long int>(8,0))))),dp2(10001,vector<vector<vector<vector<long long int>>>>(2,vector<vector<vector<long long int>>>(2,vector<vector<long long int>>(3,vector<long long int>(8,0)))));
    dp1[0][0][0][0][0] = 1;
    dp2[0][0][0][0][0] = 1;
    int x;
    REP(i,tn){
        REP(j,2){
            REP(k,2){
                REP(l,3){
                    REP(m,8){
                        x = j ? 9 : (int)(t[i] - '0');
                        REP(n,x+1){
                            dp1[i + 1][j || n < x][k || n == 3][(l + n) % 3][(m * 10 + n) % 8] += dp1[i][j][k][l][m];
                        }

                    }
                }
            }
        }

    }

    REP(i,sn){
        REP(j,2){
            REP(k,2){
                REP(l,3){
                    REP(m,8){
                        x = j ? 9 : (int)(s[i] - '0');
                        REP(n,x+1){
                            dp2[i + 1][j || n < x][k || n == 3][(l + n) % 3][(m * 10 + n) % 8] += dp2[i][j][k][l][m];
                        }

                    }
                }
            }
        }

    }

    long long int result = 0;
    REP(i,2){
        REP(j,2){
            REP(k,3){
                REP(l,8){
                    if((j||k==0)&&l!=0){
                        result += dp1[tn][i][j][k][l]-dp2[sn][i][j][k][l];
                        result %= mod;
                    }
                }
            }
        }
    }

    cout << result << endl;

    return 0;
}
0