結果

問題 No.2032 Let's Write Multiples!!
ユーザー 👑 ygussany
提出日時 2022-07-24 15:04:18
言語 C
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 1,754 bytes
コンパイル時間 1,075 ms
コンパイル使用メモリ 31,468 KB
実行使用メモリ 8,860 KB
最終ジャッジ日時 2024-07-19 02:14:11
合計ジャッジ時間 7,036 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 4 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>

int solve_enumerate(int L, int R, int K, int C)
{
	int X, Y, ans = 0;
	for (X = (L + K - 1) / K * K; X <= R; X += K) for (Y = X; Y > 0; Y /= 10) if (Y % 10 == C) ans++;
	return ans;
}

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][32001], 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 ((R - L) / K <= 32000) printf("%d\n", solve_enumerate(L, R, K, C));
		else printf("%d\n", solve_DP(R, K, C) - solve_DP(L - 1, K, C));
	}
	fflush(stdout);
	return 0;
}
0