結果

問題 No.260 世界のなんとか3
ユーザー Nzt3
提出日時 2024-04-24 14:36:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 52 ms / 2,000 ms
コード長 3,495 bytes
コンパイル時間 2,332 ms
コンパイル使用メモリ 201,316 KB
最終ジャッジ日時 2025-02-21 08:48:31
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr int MOD=1e9+7;

void ch(int &a,int b){
  a=(a+b)%MOD;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string A,B;
  cin>>A>>B;
  int LA=(int)A.size(),LB=(int)B.size();
  for(auto &i:A)i-='0';
  for(auto &i:B)i-='0';
  for(int i=LA-1;i>=0;i--){
    if(A[i]>=1){
      A[i]-=1;
      break;
    }else{
      A[i]=(A[i]+9)%10;
    }
  }
  int ans=0;
  {
    vector dp00(LA,array<int,24>());
    for(int i=0;i<LA;i++){
      for(int j=0;j<24;j++){
        dp00[i][j]=0;
      }
    }

    // 3がついている , Nより小さい
    auto dp01=dp00,dp10=dp00,dp11=dp00;
    for(int i=0;i<A[0];i++){
      if(i==3)dp11[0][i]=1;
      else dp01[0][i]=1;
    }
    if(A[0]==3)dp10[0][A[0]]=1;
    else dp00[0][A[0]]=1;
    for(int i=1;i<LA;i++){
      for(int j=0;j<24;j++){
        for(int d=0;d<10;d++){
          // 11->11
          ch(dp11[i][(j*10+d)%24],dp11[i-1][j]);
          // 01->11, 01->01
          if(d==3){
            ch(dp11[i][(j*10+d)%24],dp01[i-1][j]);
          }else{
            ch(dp01[i][(j*10+d)%24],dp01[i-1][j]);
          }
        }
      
        for(int d=0;d<A[i];d++){
          // 10->11
          ch(dp11[i][(j*10+d)%24],dp10[i-1][j]);
          if(d==3){
            // 00->11
            ch(dp11[i][(j*10+d)%24],dp00[i-1][j]);
          }else{
            // 00->01
            ch(dp01[i][(j*10+d)%24],dp00[i-1][j]);
          }
        }
        // 10->10
        ch(dp10[i][(j*10+A[i])%24],dp10[i-1][j]);
        if(A[i]==3){
          // 00->10
          ch(dp10[i][(j*10+A[i])%24],dp00[i-1][j]);
        }else{
          // 00->00
          ch(dp00[i][(j*10+A[i])%24],dp00[i-1][j]);
        }
      }
    }
    for(int i=0;i<24;i+=1){
      if(i%8==0)continue;
      ch(ans,-dp11[LA-1][i]);
      ch(ans,-dp10[LA-1][i]);
      if(i%3==0){
        ch(ans,-dp00[LA-1][i]);
        ch(ans,-dp01[LA-1][i]);
      }
    }
  }
  {
    vector dp00(LB,array<int,24>());
    for(int i=0;i<LB;i++){
      for(int j=0;j<24;j++){
        dp00[i][j]=0;
      }
    }

    // 3がついている , Nより小さい
    auto dp01=dp00,dp10=dp00,dp11=dp00;
    for(int i=0;i<B[0];i++){
      if(i==3)dp11[0][i]=1;
      else dp01[0][i]=1;
    }
    if(B[0]==3)dp10[0][B[0]]=1;
    else dp00[0][B[0]]=1;
    for(int i=1;i<LB;i++){
      for(int j=0;j<24;j++){
        for(int d=0;d<10;d++){
          // 11->11
          ch(dp11[i][(j*10+d)%24],dp11[i-1][j]);
          // 01->11, 01->01
          if(d==3){
            ch(dp11[i][(j*10+d)%24],dp01[i-1][j]);
          }else{
            ch(dp01[i][(j*10+d)%24],dp01[i-1][j]);
          }
        }
      
        for(int d=0;d<B[i];d++){
          // 10->11
          ch(dp11[i][(j*10+d)%24],dp10[i-1][j]);
          if(d==3){
            // 00->11
            ch(dp11[i][(j*10+d)%24],dp00[i-1][j]);
          }else{
            // 00->01
            ch(dp01[i][(j*10+d)%24],dp00[i-1][j]);
          }
        }
        // 10->10
        ch(dp10[i][(j*10+B[i])%24],dp10[i-1][j]);
        if(B[i]==3){
          // 00->10
          ch(dp10[i][(j*10+B[i])%24],dp00[i-1][j]);
        }else{
          // 00->00
          ch(dp00[i][(j*10+B[i])%24],dp00[i-1][j]);
        }
      }
    }
    for(int i=0;i<24;i+=1){
      if(i%8==0)continue;
      ch(ans,dp11[LB-1][i]);
      ch(ans,dp10[LB-1][i]);
      if(i%3==0){
        ch(ans,dp00[LB-1][i]);
        ch(ans,dp01[LB-1][i]);
      }
    }
  }
  ch(ans,MOD);
  cout<<ans<<'\n';
}
0