#315040 (C) No.260 世界のなんとか3

• 問題: No.260 世界のなんとか3
• ユーザー: akakimidori
• 提出日時: 2019-02-08 12:01:19
• 言語: C (gcc 12.3.0)
• 結果: WA
• 実行時間: -
• コード長: 1,556 bytes
• コンパイル時間: 882 ms
• コンパイル使用メモリ: 32,640 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-27 16:19:42
• 合計ジャッジ時間: 2,653 ms
• ジャッジサーバーID （参考情報）: judge5 / judge2

入力	結果	実行時間; 実行使用メモリ
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	38 ms; 5,376 KB
testcase_05	WA	-
testcase_06	AC	6 ms; 5,376 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	AC	11 ms; 5,376 KB
testcase_10	WA	-
testcase_11	WA	-
testcase_12	AC	18 ms; 5,376 KB
testcase_13	WA	-
testcase_14	AC	25 ms; 5,376 KB
testcase_15	AC	7 ms; 5,376 KB
testcase_16	AC	23 ms; 5,376 KB
testcase_17	WA	-
testcase_18	AC	17 ms; 5,376 KB
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
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

ソースコード

#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+=mod-1;
  }
  scanf("%s",s);
  n=strlen(s);
  int64 fb=calc(s,n);
  printf("%lld\n",(fb-fa+mod)%mod);
}

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