結果

問題 No.260 世界のなんとか3
ユーザー Nzt3Nzt3
提出日時 2024-04-24 14:36:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 51 ms / 2,000 ms
コード長 3,495 bytes
コンパイル時間 2,573 ms
コンパイル使用メモリ 208,508 KB
実行使用メモリ 6,924 KB
最終ジャッジ日時 2024-11-06 23:01:03
合計ジャッジ時間 3,942 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 42 ms
6,924 KB
testcase_04 AC 42 ms
6,916 KB
testcase_05 AC 10 ms
5,248 KB
testcase_06 AC 7 ms
5,248 KB
testcase_07 AC 30 ms
6,388 KB
testcase_08 AC 22 ms
6,656 KB
testcase_09 AC 13 ms
5,248 KB
testcase_10 AC 34 ms
6,016 KB
testcase_11 AC 31 ms
6,512 KB
testcase_12 AC 20 ms
5,752 KB
testcase_13 AC 7 ms
5,248 KB
testcase_14 AC 29 ms
6,388 KB
testcase_15 AC 9 ms
5,248 KB
testcase_16 AC 26 ms
5,740 KB
testcase_17 AC 20 ms
5,248 KB
testcase_18 AC 20 ms
5,248 KB
testcase_19 AC 25 ms
6,388 KB
testcase_20 AC 19 ms
5,248 KB
testcase_21 AC 16 ms
5,480 KB
testcase_22 AC 28 ms
5,872 KB
testcase_23 AC 4 ms
5,248 KB
testcase_24 AC 22 ms
6,136 KB
testcase_25 AC 28 ms
6,912 KB
testcase_26 AC 18 ms
6,912 KB
testcase_27 AC 2 ms
5,248 KB
testcase_28 AC 42 ms
6,916 KB
testcase_29 AC 51 ms
6,920 KB
権限があれば一括ダウンロードができます

ソースコード

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