結果

問題 No.315 世界のなんとか3.5
ユーザー piyoko_212piyoko_212
提出日時 2015-12-25 17:36:20
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 673 ms / 2,000 ms
コード長 2,659 bytes
コンパイル時間 342 ms
コンパイル使用メモリ 37,968 KB
実行使用メモリ 32,592 KB
最終ジャッジ日時 2024-09-18 23:54:17
合計ジャッジ時間 9,398 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 9 ms
31,864 KB
testcase_01 AC 11 ms
31,460 KB
testcase_02 AC 11 ms
32,092 KB
testcase_03 AC 11 ms
32,208 KB
testcase_04 AC 10 ms
31,144 KB
testcase_05 AC 12 ms
31,368 KB
testcase_06 AC 12 ms
31,948 KB
testcase_07 AC 10 ms
32,584 KB
testcase_08 AC 10 ms
31,432 KB
testcase_09 AC 10 ms
31,208 KB
testcase_10 AC 9 ms
32,264 KB
testcase_11 AC 10 ms
31,240 KB
testcase_12 AC 176 ms
31,500 KB
testcase_13 AC 183 ms
31,276 KB
testcase_14 AC 337 ms
32,516 KB
testcase_15 AC 346 ms
32,132 KB
testcase_16 AC 334 ms
32,296 KB
testcase_17 AC 333 ms
31,764 KB
testcase_18 AC 183 ms
31,364 KB
testcase_19 AC 177 ms
31,776 KB
testcase_20 AC 176 ms
32,268 KB
testcase_21 AC 175 ms
32,252 KB
testcase_22 AC 331 ms
32,144 KB
testcase_23 AC 334 ms
32,368 KB
testcase_24 AC 333 ms
32,480 KB
testcase_25 AC 335 ms
32,436 KB
testcase_26 AC 333 ms
31,492 KB
testcase_27 AC 338 ms
31,512 KB
testcase_28 AC 200 ms
32,364 KB
testcase_29 AC 516 ms
32,504 KB
testcase_30 AC 518 ms
32,148 KB
testcase_31 AC 511 ms
31,688 KB
testcase_32 AC 673 ms
32,592 KB
testcase_33 AC 336 ms
32,364 KB
testcase_34 AC 365 ms
32,556 KB
testcase_35 AC 361 ms
32,448 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:91:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   91 |         scanf("%s%s%d",A,B,&P);
      |         ~~~~~^~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
long long mod=1000000007;
char str[210000];
char A[210000];
char B[210000];
int P;
int m3[110000];
int y[110000];
int cnt[2][3];
int lim=1000;
long long dp[210000][3][2][3];
int las=0;
char tmp[10];
long long count(int t){
	for(int i=0;i<210000;i++)for(int j=0;j<3;j++)for(int k=0;k<2;k++)for(int l=0;l<3;l++)
		dp[i][j][k][l]=0;
	for(int i=1;i<10;i++){
		dp[1][i%3][i==3][(i==(str[0]-'0'))?0:((i>(str[0]-'0'))?2:1)]++;
	}
	int len=strlen(str);
	for(int i=1;i<len-las;i++){
	//printf("%c\n",str[i]);
		for(int j=0;j<3;j++)for(int k=0;k<2;k++)for(int l=0;l<3;l++){
			if(!dp[i][j][k][l])continue;
			for(int m=0;m<10;m++){
				int tj=j;
				int tk=k;
				int tl=l;
				tj=(tj+m)%3;
				if(m==3)tk=1;
				if(tl==0){
					if(m<str[i]-'0')tl=1;
					if(m>str[i]-'0')tl=2;
				}
			//	if(l==0)printf("%d %d %d %d %d %d %d %d\n",i,j,k,l,m,tj,tk,tl);
				dp[i+1][tj][tk][tl]=(dp[i+1][tj][tk][tl]+dp[i][j][k][l])%mod;
			}
		}
	}
	long long ret=0;
	if(len>las){
		for(int i=len-las;i<len;i++)tmp[i-len+las]=str[i];
		int b;
		sscanf(tmp,"%d",&b);
	//	printf("%d\n",b);
		ret+=cnt[0][0]+cnt[1][0]+cnt[1][1]+cnt[1][2];
	//	printf("%lld\n",ret);
		for(int i=1;i<=len-las;i++){
			for(int j=0;j<3;j++){
				for(int k=0;k<2;k++){
					for(int l=0;l<3;l++){
						if(!dp[i][j][k][l])continue;
						//printf("%d %d %d %d: %lld\n",i,j,k,l,dp[i][j][k][l]);
						if(i==len-las&&l==2)continue;
						if(i==len-las&&l==0){
							long long tt=0;
							for(int m=0;m<=b;m++){
								if(m%P==0)continue;
								if(t==1&&m==b)continue;
								if((m3[m]+j)%3==0||y[m]||k)tt++;
							}
					//		printf("%lld\n",tt);
							ret=(ret+tt*dp[i][j][k][l])%mod;
					//		printf("%lld\n",ret);
						}else{
							if(k==1)ret=(ret+dp[i][j][k][l]*(cnt[1][0]+cnt[1][1]+cnt[1][2]+cnt[0][0]+cnt[0][1]+cnt[0][2]))%mod;
							else ret=(ret+dp[i][j][k][l]*(cnt[1][0]+cnt[1][1]+cnt[1][2]+cnt[0][(3-j)%3]))%mod;
				//			printf("%lld\n",ret);
						}
					}
				}
			}
		}
	}else{
		int b;
		sscanf(str,"%d",&b);
		for(int i=0;i<=b;i++){
			if(i%P==0)continue;
			if(t==1&&i==b)continue;
			if(m3[i]==0||y[i])ret++;
		}
	}
	ret%=mod;
	//printf("%lld\n",ret);
	return ret;
}
int main(){
	scanf("%s%s%d",A,B,&P);
	las=3;
	if(P>10){lim*=10;las++;}
	if(P>100){lim*=10;las++;}
	for(int i=0;i<lim;i++){
		int X=0;
		int Y=0;
		if(i%P==0)continue;
		int z=i;
		while(z){
			X+=z%10;
			if(z%10==3)Y=1;
			z/=10;
		}
		X%=3;
		m3[i]=X;y[i]=Y;cnt[Y][X]++;
	}
	long long ret=0;
	for(int i=0;i<210000;i++)str[i]=B[i];
	ret=count(0);
	for(int i=0;i<210000;i++)str[i]=A[i];
	ret=(ret+mod-count(1))%mod;
	printf("%lld\n",ret);
}
0