榎本贵音


私信TA

用户名:170809011123

访问量:5923

签 名:

签名被你吃了ヽ( ̄д ̄;)ノ

等  级
排  名 3241
经  验 1881
参赛次数 21
文章发表 2
年  龄 19
在职情况 学生
学  校 西京学院
专  业 计科

  自我简介:

简介能吃么?

TA的其他文章

解题思路:


因为只要保证每个位置上的数不相同,自然可以把它们从小到大排列

所以只需从第二个数(从右往左)一直计算当前位置的排列数最后加起来就行

因为除最高位以外,别的位置的范围都是从  1 到 进制数减去当前位置
所以先计算除最高位以外的排列数,再计算最高位的排列数


注意事项:

最高位的排列数应该用减法思维,即拿k=3,w=8来说,最高位只能取1-3,实际计算的时候应该拿最高位可以取1-7的情况减去最高位可以取4-7的情况,因为假设最高位取了2,后面只能比前面大,所以此时要排除后面取1和2的情况,计算量大。如果计算4-7,则最高位和后面都只能取4-7,不存在最高位能取后面不能取的情况,即最高位和后面都只能取4-7等于从4张牌里挑3张,共4种,最高位可以取1-7即7张牌里挑3张,共35种,35减4=31


当然加法也可以做,即最高位取1加最高位取2加最高位取3,即最高位取1,后面6张挑2张,等于15,最高位取2,后面取不了1了,5张挑2张,等于10,最高位取3,后面取不了1和2了,4张挑2张,等于6,15+10+6=31


最终答案用最高位排列数加上最高位以外的排列数即 31+21=52    


参考代码:

//
//  main.cpp
//  2^k进制数
//
//  Created by 榎本贵音 on 2018/8/30.
//  Copyright © 2018年 榎本贵音. All rights reserved.
//
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
long C(int n,int m)          //C(n-1)(m)计算排列数,其中n为最大数值+1(进制),m为当前位置
{
    int i;
    long sum=1;
    for(i=1;i<=m;i++)
        sum*=(n-i);
    for(i=2;i<=m;i++)
        sum=sum/i;
    return sum;
}
int main()
{
    long sum=0;              //sum用于计算符合的总数
    int k,w,max,wei,high,i;  //max为X进制,wei为位数,high为最高位能取得的最大数,i循环用
    scanf("%d%d",&k,&w);
    max=pow(2,k);
    wei=w/k+1;               //设w不能除尽k,所以设多一位
    high=pow(2,w%k)-1;       //假设w能除尽k,最高位high能取得的最大数为0
    if(max-wei<high)
        high=max-wei;        //high既小于二进制余出来的位数所能得到的最大数又小于X进制减位数
    for(i=2;i<wei;i++)       //从第二位开始(从右往左),对每一位数(除最高位)计算排列数
    sum+=C(max,i);
    if(high!=0)
    sum+=(C(max,wei)-C(max-high,wei)); //计算最高位的排列数
    printf("%ld",sum);
    return 0;
}


 

0.0分

45 人评分

  评论区

我想问一下,有没有uu知道第50个测试用例是什么特殊值来的,我自己写的代码答案错误50。
2022-09-29 15:08:53
数据好水,答案最多就20多位,我还以为要手写高精度
2022-01-29 16:01:58
对啊,至少得有个大数吧,答案不是在200位以内?
2020-05-27 10:40:41
对啊,至少得有个大数吧?结果不是200位以内?
2020-05-27 10:40:20
作为结果的正整数可能很大,但不会超过200位.
题目中这句话有什么用,如果有一百多位,岂不是答案不能像你那样直接long表示吗?
2020-04-20 17:05:00
我炸了
2020-02-19 11:07:42
if(max-wei<high)
        high=max-wei;        //high既小于二进制余出来的位数所能得到的最大数又小于X进制减位数
这句话什么意思??
2019-03-07 21:12:04
这叫组合数吧
2019-02-28 22:18:50