結果

問題 No.260 世界のなんとか3
コンテスト
ユーザー goodbaton
提出日時 2015-08-01 00:21:48
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,116 bytes
コンパイル時間 696 ms
コンパイル使用メモリ 75,904 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-07-18 00:14:40
合計ジャッジ時間 3,141 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 WA * 24
権限があれば一括ダウンロードができます

ソースコード

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[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