結果

問題 No.260 世界のなんとか3
ユーザー goodbatongoodbaton
提出日時 2015-08-01 00:20:50
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 2,116 bytes
コンパイル時間 572 ms
コンパイル使用メモリ 74,920 KB
実行使用メモリ 10,192 KB
最終ジャッジ日時 2023-09-24 23:57:06
合計ジャッジ時間 4,227 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
9,192 KB
testcase_01 AC 5 ms
9,192 KB
testcase_02 AC 5 ms
9,176 KB
testcase_03 RE -
testcase_04 RE -
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 RE -
testcase_26 RE -
testcase_27 AC 5 ms
9,236 KB
testcase_28 RE -
testcase_29 RE -
権限があれば一括ダウンロードができます

ソースコード

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 1000000009
#define INF 2000000000
#define LLINF 4000000000000000000
#define SIZE 50010

string C;
int M;

int memo[10000][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