k好数

发表于

这是一道想了好久的题…在用贫瘠的脑袋想了半天后我决定查看网上的解法–依旧想了半天.最后,我决定用博客记录下这道题的思路

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
问题描述
  如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模后的值。

输入格式
  输入包含两个正整数，K和L。

输出格式
  输出一个整数，表示答案对1000000007取模后的值。

样例输入
  4 2
样例输出
  7
数据规模与约定
  对于30%的数据，K^L <= 106；

  对于50%的数据，K <= 16， L <= 10；

  对于100%的数据，1 <= K,L <= 100。

思路

这道题的标准解法–动态规划

L=1

先思考最简单的一种情况:L=1,即一位数的情况

此时,2进制的数只有1这一种可能;3进制的数有1 2这两种可能.以此类推…K进制的数有K-1种可能.很容易理解

L\K 1 2 3 … 可能数
1 0 1 2 … K-1

L=2

那么如果L=2呢?这时就要考虑多位数间是否符合关系了

为了简单起见,我们假设新添加的一位永远是最左边的一位,即最高位,并且使用穷举法(滑稽)

假设进制K=4.当最高位为1时,右边的数值可能为1 3;当最高位为2时,右边的数值可能为0 2;当最高位为3时,右边的数值可能是0 1 3.因此当L=2,K=4时,总共有3种可能

最高位 可能情况 可能数
0 00 02 03 3
1 11 13 2
2 20 22 2
3 30 31 33 3

总可能数为2+2+3=7种(最高位不为0因此不计在内,但之后有用)

L=3

再进一步,让位数L=3,并仍假设进制K=4

当最高位为1时,右边的数值可能为1 3,因此右边的数可能为11 13 30 31 33;以此类推…

不难发现,最高位为1时,它的可能数和L=2时的可能数相关.不妨设位数为i,最高位为j,可能数为(i,j).那么(i,j)=(i-1,j1)+(i-1,j2)+…+(i-1,jn),jn是与j不相邻的数字

最高位 可能情况 方法 可能数
1 111 113 130 131 133 (2,1)+(2,3) 5
2 200 202 203 220 222 (2,0)+(2,2) 5
3 300 302 303 311 313 330 331 333 (2,0)+(2,1)+(2,3) 8

因此总可能数为5+5+8=18

由于可能数的值均由前一项可能数推导而来,那么很容易想到用动态规划来做这道题

L=i

思路理清后,我们来重新审视一遍这道题–设位数为i,最高位的数值为j,最高位为j时的可能性为(i,j).那么可以得到(i,j)=(i-1,j1)+(i-1,j2)+...+(i-1,jn),jn是与j不相邻的数字

L=2,K=4的结果如下表格:

i\j/(i,j) 0 1 2 3
1 1 1 1 1
2 (1,0)+(1,2)+(1,3)=3 (1,1)+(1,3)=2 (1,0)+(1,2)=2 (1,0)+(1,1)+(1,3)=3

由上图,因为最高位可能为1,2,3,所以当L=2,K=4时总可能数为(2,1)+(2,2)+(2,3)=7

代码

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
long kgood(int K, int L)
{
    //表示最高位为j时的可能数
    vector<long> path(K, 1);
    for (int i = 0; i < L - 1; i++)
    {
        //tmp数组,用于更新path数组的值
        vector<long> tmp(K, 0);
        for (int j = 0; j < K; j++)
            //从0至K循环,并判断是否有效
            for (int x = 0; x < K; x++)
                if (j + 1 != x && j - 1 != x)
                {
                    tmp[j] += path[x];
                    tmp[j] %= 1000000007;
                }
        path.assign(tmp.begin(), tmp.end());
    }
    //从下标1开始累加,计算总可能数
    long sum = 0;
    for (int i = 1; i < path.size(); i++)
    {
        sum += path[i];
        sum %= 1000000007;
    }
    return sum;
}

感想

如果我自己想的话怎么都不可能想出来的,也许这就是我和算法大佬之间的差距吧-.-就我这智商不指望在算法领域能有什么成就了,只能当一个入门者了orz

0%