许健跃

用户名：Kazimierz

访问量：3260

签　名：

等　　级
排　　名	3291
经　　验	1976
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校	长江大学
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

蓝桥杯2022年第十三届省赛-统计子矩阵(前缀和暴力 and 双指针优化)
浏览：980

K-进制数(简简单单写个dfs)
浏览：120

K-进制数(排列组合解)
浏览：688

你可能喜欢

K-进制数(排列组合解)

　　作者: 许健跃　　　　发表时间：2022-09-07 11:22:58 浏览：688　|　评论：0　

原题链接：K-进制数

## 1.前言
本解需要用到高中排列组合的一些知识
## 2.题意分析
> 简而言之，本题是让我们求一个N位数($$4<=n+k<=18$$)的K(2<=k<=10)进制数,一共有多少种合法的方案。

合法性需要满足两个条件：
- 1.首位不为0
- 2.不存在两个连续的0
- 例如 当n=7 k=10时
1010230 是有效的7位数
1000198 无效
0001235 不是7位数, 而是4位数.

## 3.数学分析
### 3.1 问题描述
对于一任意的n位k进制数，它的每一位只能取0到k-1，最多取n位，并且首位不能为0，不能出现两个连续的0，问一共有多少种取法。
### 3.2 解法分析
有了上面的分析，很显然这是一道典型的排列组合问题，接下来就是如何运用数学知识解决这个问题。

$$设这个数为n位k进制数,零的个数为i(i<=n-i),解的个数为res$$

我们将0插入到由非0元素组成序列的夹缝中,这种方法俗称插空法，可以防止出现两个连续的0，因此可以满足题意
![](/image_editor_upload/20220907/20220907111017_66257.png)
接下来我们讨论0的个数
$$注：{n\choose m}表示从n个数中选m个数的方案数$$
当i=0时：此时$$res=(k-1)^n\cdot{n-0\choose 0}$$
当i=1时：此时$$res=(k-1)^{n-1}\cdot{n-1\choose 1}$$
当i=2时：此时$$res=(k-1)^{n-2}\cdot{n-2\choose 2}$$
当i=3时：此时$$res=(k-1)^{n-3}\cdot{n-3\choose 3}$$
依次类推我们将每一种情况的方案数求和便是总答案
总方案数$$\sum\limits_{i=0}^{i<=n-i} (k-1)^{n-i}\cdot{n-i\choose i}$$
## 4.具体代码
```
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
LL n,k,res;

//计算阶乘 
LL fac(int x)
{
    LL sum=1;
    for(int i=1;i<=x;i++)
	{
        sum*=i;
    }
    return sum;
}

//组合数 
LL C(int n,int m){
    return fac(n)/(fac(m)*fac(n-m));
}

int main()
{
	cin>>n>>k;
	//执行上文中推导出的公式
	for(int i=0;i+i<=n;i++)
	{
		res += pow(k-1,n-i)*C(n-i,i);
	}
	cout<<res<<endl;
	return 0;
}
```

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

许健跃

TA的其他文章

你可能喜欢

字符逆序（C语言代码）

勾股数（Java代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C二级辅导-计负均正（C语言代码）

K-进制数(排列组合解)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

WU-格式化数据输出（C++代码）

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-统计字符（C语言代码）

许健跃

TA的其他文章

你可能喜欢

字符逆序 （C语言代码）

勾股数 （Java代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C二级辅导-计负均正 （C语言代码）

K-进制数(排列组合解)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

不容易系列2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

WU-格式化数据输出 （C++代码）

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

A+B for Input-Output Practice (V) （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-统计字符 （C语言代码）

字符逆序（C语言代码）

勾股数（Java代码）

C二级辅导-计负均正（C语言代码）

　　评论区

WU-格式化数据输出（C++代码）

母牛的故事（C语言代码）

C二级辅导-统计字符（C语言代码）