結果

問題 No.315 世界のなんとか3.5
ユーザー ooaiu
提出日時 2025-08-17 18:59:17
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,151 bytes
コンパイル時間 3,630 ms
コンパイル使用メモリ 293,320 KB
実行使用メモリ 814,464 KB
最終ジャッジ日時 2025-08-17 18:59:34
合計ジャッジ時間 15,483 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12 TLE * 2 MLE * 3 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::static_modint<7+(int)1e9>;
using ll = long long;
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	string A,B;
	cin>>A>>B;
	int P;
	cin>>P;
	int c2=1,c5=1;
	while(P%(c2*2)==0)c2*=2;
	while(P%(c5*5)==0)c5*=5;
	auto solve=[&](const string&S){
		int N=S.size();
		vector dp(N+1,vector(2,vector(c2,vector(c5, vector(3, vector<mint>(2))))));
		dp[0][0][0][0][0][0]=1;
		for(int i=0;i<N;i++)for(int less=0;less<2;less++)for(int j=0;j<c2;j++)for(int k=0;k<c5;k++){
			for(int c3=0;c3<3;c3++)for(int h3=0;h3<2;h3++)if(dp[i][less][j][k][c3][h3].val()){
				int lim=less?9:S[i]-'0';
				for(int d=0;d<=lim;d++){
					dp[i+1][less||d<lim][(j*10+d)%c2][(k*10+d)%c5][(c3+d)%3][h3||d==3] += dp[i][less][j][k][c3][h3];
				}
			}
		}
		return dp[N];
	};
	auto dpA=solve(A);
	auto dpB=solve(B);
	mint ans=0;
	for(int c3=0;c3<3;c3++)for(int h3=0;h3<2;h3++)for(int i=0;i<c2;i++)for(int j=0;j<c5;j++)if(c3==0||h3){
		if(i==0&&j==0)continue;
		for(int k=0;k<2;k++)ans+=dpB[k][i][j][c3][h3];
		ans-=dpA[1][i][j][c3][h3];
	}
	cout<<ans.val()<<"\n";
}
0