Fork me on GitHub

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

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

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，因为要求数字中不能出现0和3，那么遍历时直接去除这两个数字就可以了。最后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%