結果

問題 No.315 世界のなんとか3.5
ユーザー piyoko_212piyoko_212
提出日時 2015-12-25 17:18:10
言語 C++11
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,469 bytes
コンパイル時間 334 ms
コンパイル使用メモリ 37,424 KB
実行使用メモリ 32,772 KB
最終ジャッジ日時 2024-09-18 23:52:52
合計ジャッジ時間 27,550 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 8 WA * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:86:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   86 |         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++){
		for(int j=0;j<3;j++)for(int k=0;k<2;k++)for(int l=0;l<3;l++){
			for(int m=0;m<10;m++){
				int tj=j;
				int tk=k;
				int tl=l;
				tj=(tj+m)%mod;
				if(m==3)tk=1;
				if(tl==0){
					if(m<str[i]-'0')tl=1;
					if(m>str[i]-'0')tl=2;
				}
				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(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++;
							}
							ret=(ret+tt*dp[i][j][k][l])%mod;
					//		printf("%lld\n",ret);
						}else{
					//		printf("%d %d %d %d: %lld\n",i,j,k,l,dp[i][j][k][l]);
							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