結果

問題 No.2032 Let's Write Multiples!!
ユーザー ygussanyygussany
提出日時 2022-07-24 15:47:18
言語 C
(gcc 12.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 AC 50 ms
6,940 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 TLE -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
権限があれば一括ダウンロードができます

ソースコード

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