UC知道k好数（c++）排列组合算法
来源：百度知道 编辑：UC知道 时间：2024/05/11 12:45:18
K好数（K-Good Number）
问题描述：
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。给定K、L，求L位K好数的数目。
输入格式：
从文件读入数据，第一行为K、L，其中K<=16，L<=10。
输出格式：
将结果输出到 KGOOD.OUT
样例
KGOOD.DAT KGOOD.OUT
4 2
7
主要能给我一个排列组合公式，不然会超时！！
老师给的时间太少
问题描述：
如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。给定K、L，求L位K好数的数目。
输入格式：
从文件读入数据，第一行为K、L，其中K<=16，L<=10。
输出格式：
将结果输出到 KGOOD.OUT
样例
KGOOD.DAT KGOOD.OUT
4 2
7
主要能给我一个排列组合公式，不然会超时！！
老师给的时间太少
？从最小到最大循环一遍也会超时……？
看来是一道简单的acm题目了……那个你不觉得这个应该自己想？
当L＝2时，N=(K-2)^2+K-1;
记为N(K,2);
N(K,3)=(K-1)*N(K,2)-2*N(K,1);
N(K,n)=(K-1)*N(K,n-1)-2*N(K,n-2);
好了，就这么回事，你递归吧……
我应该是没算错的哈……
这里N(K,1)=K-1
不包括0的