結果

問題 No.260 世界のなんとか3
コンテスト
ユーザー alumina_8
提出日時 2019-03-28 19:50:16
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,754 bytes
コンパイル時間 1,314 ms
コンパイル使用メモリ 141,232 KB
実行使用メモリ 32,640 KB
最終ジャッジ日時 2024-11-30 13:48:01
合計ジャッジ時間 5,226 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 WA * 23 RE * 2
権限があれば一括ダウンロードができます

ソースコード

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