要求计算出不包括相邻的零的 N 位 K-进制数共有多少个

admin - 2008-7-4 22:04:00

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 successful 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 ≤ 1800.

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

OutputThe result in decimal notation.

Sample

input	output
2 10	90

答案如下：
1 using System;
2
3 namespace Skyiv.Ben.Timus
4 {
5 //http://acm.timus.ru/problem.aspx?space=1&num=1013
6 sealed class T1013
7 {
8 static void Main()
9 {
10 int n = int.Parse(Console.ReadLine()), i = 2;
11 int k = int.Parse(Console.ReadLine()) - 1;
12 BigInteger m = 0;
13 for (BigInteger p = 1, q = k; i <= n; i++, p = q, q = m) m = (p + q) * k;
14 Console.WriteLine(m);
15 }
16 }
17
18 sealed class BigInteger
19 {
20 int[] digits = new int[1800];
21
22 public BigInteger(int n)
23 {
24 digits[0] = n;
25 if (digits[0] > 9) Format();
26 }
27
28 public BigInteger(BigInteger x)
29 {
30 Array.Copy(x.digits, digits, digits.Length);
31 }
32
33 public static implicit operator BigInteger(int x)
34 {
35 return new BigInteger(x);
36 }
37
38 public static BigInteger operator +(BigInteger x, BigInteger y)
39 {
40 BigInteger z = new BigInteger(x);
41 for (int i = x.digits.Length - 1; i >= 0; i--) z.digits= x.digits + y.digits;
42 z.Format();
43 return z;
44 }
45
46 public static BigInteger operator *(BigInteger x, int y)
47 {
48 BigInteger z = new BigInteger(x);
49 for (int i = x.digits.Length - 1; i >= 0; i--) z.digits = x.digits * y;
50 z.Format();
51 return z;
52 }
53
54 void Format()
55 {
56 for (int quotient = 0, i = 0; i < digits.Length; i++)
57 {
58 int numerator = digits + quotient;
59 quotient = numerator / 10;
60 digits = numerator % 10;
61 }
62 }
63
64 public override string ToString()
65 {
66 int n = digits.Length - 1;
67 while (n >= 0 && digits[n] == 0) n--;
68 if (n < 0) return "0";
69 char[] cs = new char[n + 1];
70 for (int i = n; i >= 0; i--) cs = (char)(digits[n - i] + '0');
71 return new string(cs);
72 }
73 }
74 }

这道题要求计算出不包括相邻的零的 N 位 K-进制数共有多少个。这里 2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 1800。
我们还是开始找规律吧。左图是 K = 4，N = 3 的情况。
我们用 Mn 来表示 n 位 K-进制数的数量。从左图中可以看出：
M2 = 12, M3 = 45
经过仔细观察，我们假设：
M0 = 1, M1 = 3
然后再经过认真分析，我们得到以下规律：
M0 = 1, M1 = K - 1, Mn = (K - 1) * (Mn-1 + Mn-2) (n > 1)

在递推公式 Mn = (K - 1) * (Mn-1 + Mn-2) 中：
系数 K - 1 代表 K-进制数的最高位从 1 到 K - 1
Mn-1 代表次高位不为零的情形
Mn-2 表示次高位为零的情形
然后，对于 K = 2、K = 3 在 N 比较小的情况下验证了这个规律。
既然有了递推公式，写出相应的程序自然易如反掌。
但是，要注意，当 K = 10，N = 1790 时，M1790 接近 101790，所以要使用 BigInteger 类来进行计算。
实际上，这个问题共有三姐妹，分别是：

1009. K-based numbers	时间限制:1.0 秒	2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 18
1012. K-based numbers. Version 2	时间限制:1.0 秒	2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 180
1013. K-based numbers. Version 3	时间限制:2.0 秒	2 ≤ K ≤ 10; N ≥ 2; N + K ≤ 1800

当然，上面的程序也完全适用于 Timus 1009 和 Timus 1012。
另外，对于 Timus 1009，把上面程序 Main() 方法中的第 12 和 13 行中的 BigInteger 改为 int 也完全没有问题。因为 int.MaxValue = 2,147,483,647，而我们有：

N	K	M
16	2	1,597
15	3	2,781,184
14	4	104,879,772
13	5	661,766,144
12	6	1,413,765,625
11	7	1,434,392,064
10	8	837,677,687
9	9	317,882,368
8	10	85,096,170

从上表中可以看出，Timus 1009 的输出绝对不会大于 1,434,392,064，所以使用 int 是安全的。
下面是这个程序的运行情况：

其中 ID 为 2147015 的记录就是把 BigInteger 改为 int 后的程序的运行结果，运行时间为 0.093 秒。这个结果有点奇怪，因为她比使用 BigInteger 的程序的运行时间 0.078 秒还要大。因为一般来说，用 int 进行运算应该比 BigInteger 快才对。

修改后的程序如下所示：
1 using System;
2
3 namespace Skyiv.Ben.Timus
4 {
5 // http://acm.timus.ru/problem.aspx?space=1&num=1009
6 sealed class T1009
7 {
8 static void Main()
9 {
10 int m = 0, n = int.Parse(Console.ReadLine());
11 int k = int.Parse(Console.ReadLine()) - 1;
12 for (int i = 2, p = 1, q = k; i <= n; i++, p = q, q = m) m = (p + q) * k;
13 Console.WriteLine(m);
14 }
15 }
16 }

星辰.Net技术社区论坛