結果

問題 No.260 世界のなんとか3
ユーザー goodbatongoodbaton
提出日時 2015-08-01 00:29:56
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 125 ms / 2,000 ms
コード長 2,115 bytes
コンパイル時間 950 ms
コンパイル使用メモリ 75,532 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-11-07 18:06:33
合計ジャッジ時間 3,415 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 6 ms
9,216 KB
testcase_01 AC 6 ms
9,088 KB
testcase_02 AC 6 ms
9,216 KB
testcase_03 AC 125 ms
10,496 KB
testcase_04 AC 122 ms
10,624 KB
testcase_05 AC 29 ms
9,728 KB
testcase_06 AC 22 ms
9,472 KB
testcase_07 AC 85 ms
10,496 KB
testcase_08 AC 62 ms
10,496 KB
testcase_09 AC 36 ms
9,856 KB
testcase_10 AC 94 ms
10,368 KB
testcase_11 AC 89 ms
10,368 KB
testcase_12 AC 58 ms
10,240 KB
testcase_13 AC 21 ms
9,216 KB
testcase_14 AC 82 ms
10,496 KB
testcase_15 AC 25 ms
9,472 KB
testcase_16 AC 73 ms
10,112 KB
testcase_17 AC 58 ms
9,984 KB
testcase_18 AC 56 ms
9,728 KB
testcase_19 AC 72 ms
10,496 KB
testcase_20 AC 52 ms
9,856 KB
testcase_21 AC 48 ms
9,984 KB
testcase_22 AC 80 ms
10,112 KB
testcase_23 AC 12 ms
9,216 KB
testcase_24 AC 65 ms
10,240 KB
testcase_25 AC 38 ms
10,624 KB
testcase_26 AC 37 ms
10,368 KB
testcase_27 AC 6 ms
9,088 KB
testcase_28 AC 65 ms
10,624 KB
testcase_29 AC 64 ms
10,496 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cstring>


using namespace std;
typedef long long ll;

#define mod 1000000007
#define INF 2000000000
#define LLINF 4000000000000000000
#define SIZE 50010

string C;
int M;

int memo[10003][3][8][2][3];

// f=0...ALL&&hmax 1...-1&&hmax 2...all&h-1

int dfs(int h,int m3,int m8,int use3,int f,int last){
    
    ll ret=0;
    if(memo[h][m3][m8][use3][f]) return memo[h][m3][m8][use3][f];
    
    if(h>0 && m8!=0 && (m3==0 || use3)) ret=1;
    
    if(h==C.size() || (h==C.size()-1 && f==2)){
        return memo[h][m3][m8][use3][f]=(int)ret;
    }
    
    int s=0;
    if(h==0) s=1;
    
    if(f==0){
    
        for(int i=s;i<=9;i++){
            ret +=dfs(h+1,(m3*10+i)%3,(m8*10+i)%8,use3 || i==3,0,i);
        }
        
    }else if(f==1){
        
        for(int i=s;i<C[h]-'0';i++){
            ret +=dfs(h+1,(m3*10+i)%3,(m8*10+i)%8,use3 || i==3,0,i);
        }
        
        ret +=dfs(h+1,(m3*10+(C[h]-'0'))%3,(m8*10+(C[h]-'0'))%8,use3 || C[h]=='3',1,(C[h]-'0'));

        if(h==C.size()-1) return memo[h][m3][m8][use3][f]=(int)(ret%mod);
        
        for(int i=C[h]-'0'+1;i<=9;i++){
            ret +=dfs(h+1,(m3*10+i)%3,(m8*10+i)%8,use3 || i==3,2,i);
        }
        
    }else{
        
        for(int i=s;i<=9;i++){
            ret +=dfs(h+1,(m3*10+i)%3,(m8*10+i)%8,use3 || i==3,2,i);
        }
    }
    
    return memo[h][m3][m8][use3][f]=(int)(ret%mod);
}

int main(){
    ll ans=0;
    string A,B;
    
    cin >>A >>B;
    
    A[A.size()-1]--;
    
    for(int i=(int)A.size()-1;i>=0;i--){
        if(A[i]<'0'){
            A[i]='9';
            A[i-1]--;
        }else{
            break;
        }
    }
    
    if(A[0]=='0') A.erase(A.begin());
    
    C = B;
    ans+=dfs(0,0,0,0,1,-1)+mod;
    
    memset(memo, 0, sizeof(memo));
    
    if(A.size()){
        C = A;
        ans-=dfs(0,0,0,0,1,-1);
    }
    
    
    
    printf("%lld\n",ans%mod);
    
    return 0;
}
0