自动搬运

查看原文

来自洛谷，原作者为

	览遍千秋 将伤与泪汇成力化作拳

搬运于2025-08-24 22:44:30，当前版本为作者最后更新于2023-02-06 00:16:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

递推。

记 $f(i,j)$ 代表所有的 $i$ 位数，对 $k$ 取模余 $j$ 的数目。

枚举 $i$ 位数最高位上填的数 $p$，显然有 $p = 1, 2, \cdots ,9$。

很容易求出 $p \times 10^{i-1}$ 对 $k$ 取模的值，记为 $R$。

则 $f(i,j)=\sum\limits_{a=1}^{i=1}f(a,(j-R) \bmod k)$。

对于每一个 $j$，前缀和累加 $f(i,j)$ 即可，时间复杂度为 $O(nk)$。

需要注意的是，答案模数为 $100000007$，即 $10^8+7$，一个优秀的 OIer 是会数数字位数的。

Codes

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5000 + 7;
const int MAXK = 1000 + 7;
const int mod = 100000007; 

int n, k;
long long f[MAXN][MAXK];
long long sum[MAXK];

int main() {
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= 9; i++) f[1][i % k]++, sum[i % k]++;
	if(n == 1) {
		for(int i = 0; i < k; i++) {
			printf("%lld%c", f[n][i], " \n"[i == k - 1]);
		}
		return 0;
	}
	
	long long mul = 1;
	for(int i = 2; i <= n; i++) {
		mul = mul * 10 % k;
		for(int j = 1; j <= 9; j++) {
			long long val = j * mul % k;
			for(int p = 0; p < k; p++) {
				long long to = (p + val) % k;
				f[i][to] = (f[i][to] + sum[p]) % mod;
			}
			f[i][val]++;
		}
		for(int j = 0; j < k; j++) sum[j] += f[i][j], sum[j] %= mod;
	}
	for(int i = 0; i < k; i++) {
		printf("%lld%c", f[n][i], " \n"[i == k - 1]);
	}
	return 0;
}