pingfan443

用户名：liu971294083

访问量：32798

签　名：

楼上的别敲了，我跟不上

等　　级
排　　名	130
经　　验	7643
参赛次数	6
文章发表	51
年　　龄	21
在职情况	学生
学　　校	b站
专　　业	软件开发

　　自我简介：

搁劲学

TA的其他文章

蓝桥杯基础练习-十六进制转八进制 -题解(C++代码)
浏览：2883

蓝桥杯基础练习-十六进制转十进制 -题解(C语言代码)
浏览：443

蓝桥杯基础练习-十进制转十六进制-题解(C语言代码)
浏览：790

你可能喜欢

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

2^k进制数-题解(C语言代码)

　　作者: pingfan443　　　　发表时间：2020-01-30 22:57:26 浏览：593　|　评论：0　

原题链接：2^k进制数

**前序**：万幸的我花了半天时间弄懂题意，半天时间看别人代码，找思路，自己再写，最后懂了是懂了，写出来的代码错误50%，就在想放弃的时候又想到了一个代码bug，好在自己改动了一下，AC了，因此来写一下思路，希望路过的可以帮到你。最后呢建议先把题意读懂了，把测试样例在本上跑一遍，大致懂了来看题解可能会事半功倍
**思路**：自己组织语言有限，就将他人思路拷贝一下过来：[传送门](https://blog.csdn.net/Android66666/article/details/102058153 "传送门")
以下分两种情况
![](/image_editor_upload/20200130101100_71828.png)
对以上两种情况进行说明：
**第一种情况**说明之前先拿样例做个例子，k=3，w=7长度为7的0或1字符串被分成了（w/k+1）3段,我们先分析(w/k)2段的选取方案，这两段组成一个两位数，范围就是1~2^k-1，那我们就是从1~7选2个数看有多少种符合的即C(7,2)=21。（C(2^k-1,i)我们的i就是从2开始到w/k）。
**第二种情况**：我们通过max=pow(2,w%k)-1,（w%k是长度为7被分成3段，最左边那段含有的位数）来判断有没有第二种情况max=0代表最左边的那段没有位数就时没有了这种情况（我们之所以分两种情况是因为最高位这一段有可能跟其他段的取值范围不同所以特殊考虑他）所以最高位的范围是<=pow(2,w%k)-1,如果max=0,就代表它被归为第一种情况了，现在max=1,那么就是去3位数因为最高位只能等于1所以转换成1 0 0(0可换成其他数)那就是从(pow(2,k)-i-1)6中选（w/k）2个数（其中的i=1）C(6,2)=15
总方案数36
注意事项：
- 我们在计算组合数的时候C(n,m)m<=n没有这种情况会错50%
- 我在写组合数的函数采用了进行约分处理（参考紫书），同时判断m<=n。

````cpp
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll C(int n,int m)//这里采用了约分避免溢出
{
	if(m>n)return 0;//这是最重要的，没有这个错误50% 
	else
	{
		ll ans=1;
		if(m<n-m)
		m=n-m;
		for(int i=m+1;i<=n;i++)
		ans*=i;
		for(int i=1;i<=n-m;i++)
		ans/=i;
		return ans;
	}
}
int main()
{
	int k,w,max;//max在第二种情况下高位取的最大值 
	ll ans=0;
	scanf("%d%d",&k,&w);
	for(int i=2;i<=w/k;i++)//w/k是分成的段 
	ans+=C(pow(2,k)-1,i);
	max=pow(2,w%k)-1;
	for(int i=1;i<=max;i++)
	ans+=C(pow(2,k)-1-i,w/k);
	printf("%lld\n",ans);

return 0;
}

````
代码就是根据别人总结出来的两种情况来写的，大家可以尝试一下。
说明：以上代码在本网站能AC,去洛谷只能拿50分，具体原因我盲猜以下，可能是组合数那出了问题，洛谷给的数据比较大，尽管结果没超范围但是中间结果还是超了范围（有幸下载了一组没过数据 ，输入：5 2000 输出：2147483616）
总结：看了很多人的思路，自己的知识还不够，楼上的思路在处理组合数那段没有弄懂（那里应该也是避免溢出），自己总结写了一下自己的思路。
~~待更~~

0.0分

4 人评分

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

pingfan443

TA的其他文章

你可能喜欢

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

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

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

求圆的面积（C语言代码）

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

2^k进制数-题解(C语言代码)

评论区

精彩推荐

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

DNA （C++代码）

【偶数求和】（C++代码）

大神老白（C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

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

校门外的树（C语言代码）

WU-拆分位数（C++代码）

【明明的随机数】（C语言代码）

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

pingfan443

TA的其他文章

你可能喜欢

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

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

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

求圆的面积 （C语言代码）

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

2^k进制数-题解(C语言代码)

评论区

精彩推荐

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

DNA （C++代码）

【偶数求和】 （C++代码）

大神老白 （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

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

校门外的树 （C语言代码）

WU-拆分位数 （C++代码）

【明明的随机数】 （C语言代码）

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

求圆的面积（C语言代码）

　　评论区

【偶数求和】（C++代码）

大神老白（C语言代码）

校门外的树（C语言代码）

WU-拆分位数（C++代码）

【明明的随机数】（C语言代码）