URAL 1009. K-based Numbers

Author: 2015-09-14

ACM

, ,

1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1009

1009. K-based Numbers

Time limit: 1.0 second
Memory limit: 64 MB
Let’s consider K-based numbers, containing exactly N digits. We define a number to be valid if its K-based notation doesn’t contain two successive zeros. For example:

  • 1010230 is a valid 7-digit number;
  • 1000198 is not a valid number;
  • 0001235 is not a 7-digit number, it is a 4-digit number.
Given two numbers N and K, you are to calculate an amount of valid K based numbers, containing N digits.
You may assume that 2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 18.

Input

The numbers N and K in decimal notation separated by the line break.

Output

The result in decimal notation.

Sample

input output 
2
10

90
Problem Source: USU Championship 1997

2. 思路

给出位数N和进制K，求N位K进制数的个数，要求最高位不为0，且不允许两个0连续出现。

动态规划。使用cnt[i][0]表示从左向右数第i位为0时，前i位K进制数的个数；cnt[i][1]表示从左向右数第i位为0时，前i位K进制数的个数。有：

  • 当i = 1时，只有1位，该位不能为0，故有cnt[1][0] = 0和cnt[1][1] = k – 1。
  • 当i > 1时：
    • 如果第i位为0，则第i – 1位一定不是0，此时有cnt[i][0] = cnt[i – 1][1]个数字。
    • 如果第i位非0，则第i位共有k – 1种选择，对第i – 1位没有要求，此时有cnt[i][1] = (cnt[i – 1][1] + cnt[i – 1][0]) * (k – 1)个数字。

即：

cnt[1][0] = 0，
cnt[1][1] = k - 1，
cnt[i][0] = cnt[i - 1][1], i > 1,
cnt[i][1] = (cnt[i - 1][1] + cnt[i - 1][0]) * (k - 1), i > 1.

3. 代码

#include <cstdio>

const int MAX_N = 19;

void solveE6f_KBasedNumbers();

int main() {
    solveE6f_KBasedNumbers();
}

int cnt[MAX_N][2];
void solveE6f_KBasedNumbers() {
    int n, k;
    scanf("%d%d", &n, &k);
    
    cnt[1][0] = 0;
    cnt[1][1] = k - 1;
    for (int i = 2; i <= n; ++i) {
        cnt[i][0] = cnt[i - 1][1];
        cnt[i][1] = (cnt[i - 1][1] + cnt[i - 1][0]) * (k - 1);
    }
    
    printf("%d\n", cnt[n][0] + cnt[n][1]);
}