Fork me on GitHub

程序设计竞赛:讨厌的数字

Problem D. 讨厌的数字

时间限制 1000 ms
内存限制 64 MB

题目描述

奶牛的生日快到了,你准备送给他一个数x作为生日礼物,x是十进制下的一个n位数,但是奶牛向你提出了一些要求。 1 奶牛准备了一个数字d,他希望x是d的倍数 2 奶牛不喜欢0和3,他不希望x中有0或3 请问有多少个不同的n位数可以作为奶牛的生日礼物呢? 答案mod1000000007输出。

输入数据

两个数字n和d,代表数字位数和奶牛给出的数字d
0 <= n <= 1000
0 <= d <= 1000

输出数据

一个1000000007之内的整数代表答案

样例输入

1
2 3

样例输出

1
22

题解

dp[i][j]表示i位数中模d等于j的方案数。首先计算只有一位数时,满足条件的方案数作为初始值。然后依次遍历i位数下对d求余为j的方案个数;每增加一位数,就在其最后加k,因为要求数字中不能出现03,那么遍历时直接去除这两个数字就可以了。最后n位数下是d的倍数的方案个数就是dp[n][0]

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

const int maxN = 1010;
int n, d, dp[maxN][maxN];
int i, j, k;

int main() {
cin >> n >> d;
// 计算一位数的方案数
for (k = 1; k <= 9; k++) {
if (k == 3) {
continue;
}
dp[1][k % d]++;
}
// dp[i][j]表示i位数中模d等于j的方案数
for (i = 2; i <= n; i++) {
for (j = 0; j < d; j++) {
for (k = 1; k <= 9; k++) {
if (k == 3) {
continue;
}
dp[i][(j * 10 + k) % d] += dp[i - 1][j];
dp[i][(j * 10 + k) % d] %= 1000000007;
}
}
}
cout << dp[n][0] << endl;// 输出n位数中能被d整除的满足条件的方案数
return 0;
}
0%