結果

問題 No.260 世界のなんとか3
ユーザー akakimidoriakakimidori
提出日時 2019-02-08 12:04:53
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 39 ms / 2,000 ms
コード長 1,564 bytes
コンパイル時間 1,049 ms
コンパイル使用メモリ 32,768 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-27 16:23:47
合計ジャッジ時間 1,751 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 39 ms
5,376 KB
testcase_04 AC 39 ms
5,376 KB
testcase_05 AC 8 ms
5,376 KB
testcase_06 AC 6 ms
5,376 KB
testcase_07 AC 26 ms
5,376 KB
testcase_08 AC 18 ms
5,376 KB
testcase_09 AC 11 ms
5,376 KB
testcase_10 AC 29 ms
5,376 KB
testcase_11 AC 28 ms
5,376 KB
testcase_12 AC 17 ms
5,376 KB
testcase_13 AC 6 ms
5,376 KB
testcase_14 AC 26 ms
5,376 KB
testcase_15 AC 7 ms
5,376 KB
testcase_16 AC 23 ms
5,376 KB
testcase_17 AC 18 ms
5,376 KB
testcase_18 AC 17 ms
5,376 KB
testcase_19 AC 23 ms
5,376 KB
testcase_20 AC 16 ms
5,376 KB
testcase_21 AC 14 ms
5,376 KB
testcase_22 AC 25 ms
5,376 KB
testcase_23 AC 3 ms
5,376 KB
testcase_24 AC 20 ms
5,376 KB
testcase_25 AC 20 ms
5,376 KB
testcase_26 AC 20 ms
5,376 KB
testcase_27 AC 1 ms
5,376 KB
testcase_28 AC 38 ms
5,376 KB
testcase_29 AC 39 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef long long int int64;

const int mod=1000000007;

#define POS(i,j,k,l) (((((i)&1)*3+((j)%3))*2+(k))*8+((l)%8))

int64 calc(const char *s,int n){
  int64 *dp=(int64 *)calloc(2*3*2*8,sizeof(int64));
  int sup3=0;
  int sup3cond=0;
  int sup8=0;
  for(int i=0;i<n;i++){
    int j,k,l;
    for(j=0;j<3;j++) for(k=0;k<2;k++) for(l=0;l<8;l++) dp[POS(i+1,j,k,l)]=0;
    for(j=0;j<3;j++){
      for(k=0;k<2;k++){
	for(l=0;l<8;l++){
	  for(int d=0;d<10;d++){
	    int index=POS(i+1,10*j+d,k||d==3,10*l+d);
	    dp[index]+=dp[POS(i,j,k,l)];
	    dp[index]%=mod;
	  }
	}
      }
    }
    for(int d=0;d<s[i]-'0';d++){
      int index=POS(i+1,10*sup3+d,sup3cond||d==3,10*sup8+d);
      dp[index]=(dp[index]+1)%mod;
    }
    sup3=(10*sup3+s[i]-'0')%3;
    sup3cond=(sup3cond||s[i]=='3');
    sup8=(10*sup8+s[i]-'0')%8;
  }
  int64 res=((sup3==0 || sup3cond) && sup8!=0);
  int j,k,l;
  for(j=0;j<3;j++){
    for(k=0;k<2;k++){
      for(l=0;l<8;l++){
	if((j==0 || k) && l!=0) res=(res+dp[POS(n,j,k,l)])%mod;
      }
    }
  }
  return res;
}

void run(void){
  const int m=10000;
  char *s=(char *)calloc(m+1,sizeof(char));
  scanf("%s",s);
  int n=strlen(s);
  int64 fa=calc(s,n);
  int f3=0;
  int c3=0;
  int f8=0;
  for(int i=0;i<n;i++){
    f3=(10*f3+s[i]-'0')%3;
    c3=(c3||s[i]=='3');
    f8=(10*f8+s[i]-'0')%8;
  }
  if((f3==0 || c3) && f8!=0){
    fa=(fa+mod-1)%mod;
  }
  scanf("%s",s);
  n=strlen(s);
  int64 fb=calc(s,n);
  printf("%lld\n",(fb-fa+mod)%mod);
}

int main(void){
  run();
  return 0;
}
0