結果

問題 No.2032 Let's Write Multiples!!
コンテスト
ユーザー 👑 ygussany
提出日時 2022-07-24 15:47:18
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,455 bytes
コンパイル時間 527 ms
コンパイル使用メモリ 31,616 KB
実行使用メモリ 13,884 KB
最終ジャッジ日時 2024-07-06 10:23:01
合計ジャッジ時間 5,605 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 1 WA * 4 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

const int dig[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};

int solve_DP(int R, int K, int C)
{
	static int dp[2][1001], r[10];
	int d, i, j, k, RR, cur, prev, ans = 0;
	for (d = 0, RR = R; RR > 0; d++, RR /= 10) r[d] = RR % 10;
	for (k = 0; k < K; k++) {
		dp[0][k] = 0;
		dp[1][k] = 0;
	}
	for (d--, cur = 1, prev = 0; d >= 0; d--, cur ^= 1, prev ^= 1) {
		for (k = 0; k < K; k++) dp[cur][k] = 0;
		for (k = 0; k < K; k++) {
			if (dp[prev][k] == 0) continue;
			for (i = 0, j = k * 10 % K; i <= 9; i++, j++) {
				if (j == K) j = 0;
				dp[cur][j] += dp[prev][k];
				if (i == C) {
					if (j * dig[d] % K != 0) ans += dp[prev][k] * ((dig[d] - 1 + j * dig[d] % K) / K);
					else ans += dp[prev][k] * ((dig[d] - 1 + K) / K);
				}
			}
			dp[prev][k] = 0;
		}
		for (i = 0, j = RR * 10 % K; i < r[d]; i++, j++) {
			if (j == K) j = 0;
			dp[cur][j]++;
			if (i == C) {
				if (j * dig[d] % K != 0) ans += (dig[d] - 1 + j * dig[d] % K) / K;
				else ans += (dig[d] - 1 + K) / K;
			}
		}
		if (j == K) j = 0;
		RR = j;
		if (r[d] == C) {
			if (j * dig[d] % K != 0) ans += (R % dig[d] + j * dig[d] % K) / K;
			else ans += (R % dig[d] + K) / K;
		}
	}
	return ans;
}

int main()
{
	int T, L, R, K, C;
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d %d %d", &L, &R, &K, &C);
		if (K <= 700) printf("%d\n", solve_DP(R, K, C) - solve_DP(L - 1, K, C)); // 750 -> TLE
	}
	fflush(stdout);
	return 0;
}
0