結果

問題 No.260 世界のなんとか3
ユーザー akakimidori
提出日時 2019-02-08 12:04:53
言語 C
(gcc 13.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

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