好儿郎-志在四方 2016-03-16 13:58 采纳率: 100%
浏览 5817
已采纳

蓝桥杯 历届试题 公式求值 (想了很久了,想不明白,才来请教的,麻烦各位了)

图片说明

问题描述
  输入n, m, k,输出下面公式的值。

  其中C_n^m是组合数,表示在n个人的集合中选出m个人组成一个集合的方案数。组合数的计算公式如下。

输入格式
  输入的第一行包含一个整数n;第二行包含一个整数m,第三行包含一个整数k。
输出格式
  计算上面公式的值,由于答案非常大,请输出这个值除以999101的余数。
样例输入
3
1
3
样例输出
162
样例输入
20
10
10
样例输出
359316
数据规模和约定
  对于10%的数据,n≤10,k≤3;
  对于20%的数据,n≤20,k≤3;
  对于30%的数据,n≤1000,k≤5;
  对于40%的数据,n≤10^7,k≤10;
  对于60%的数据,n≤10^15,k ≤100;
  对于70%的数据,n≤10^100,k≤200;
  对于80%的数据,n≤10^500,k ≤500;
  对于100%的数据,n在十进制下不超过1000位,即1≤n<10^1000,1≤k≤1000,同时0≤m≤n,k≤n。
提示
  999101是一个质数;
  当n位数比较多时,绝大多数情况下答案都是0,但评测的时候会选取一些答案不是0的数据;

我写的代码如下:

#include
using namespace std;

unsigned long long factorial(unsigned long long f)
{
unsigned long long sum=1;
while(f>1)
{
sum=sum*f;
f--;
}
return sum;
}
unsigned long long power(unsigned long long a,unsigned long long b)
{
unsigned long long sum=1;
while(b>0)
{
sum=sum*a;
b--;
}

return sum;
}

int main()
{
unsigned long long n,m,k;
unsigned long long i=1;
unsigned long long C1=0,C2=0,C3=0;
unsigned long long sum=0;

cin >>n>>m>>k;

C2=factorial(n)/(factorial(m)*factorial(n-m));  //求C_n^m

for(i=1;i<=n;i++)
{
    C1=factorial(n)/(factorial(i)*factorial(n-i));  //求C_n^i
    C3=power(i,k);  //求i^k 
    sum=sum+C1*C2*C3;       
}   
cout<<sum<<endl;
cout<<sum%999101<<endl;
return 0; 

}
这是蓝桥杯的OJ地址:
http://lx.lanqiao.org/problem.page?gpid=T43
应该要注册才能用吧,谢谢各位大牛了。

  • 写回答

5条回答

  • cxsmarkchan 2016-03-16 15:16
    关注

    这个题有些复杂,我也没做过,但有些思路可以供你参考。
    这题涉及大组合数取模的问题。从你的代码来看,你没有使用高精度,即使代码完全正确,最多也只能过20%的数据(即n <= 20的数据)。再大的数据,long long类型根本存不下。
    由于题目中n最多有可能达到1000位十进制整数(long long类型只有20位而已),即10^1000,所以不可能采用逐个计算组合数,求和之后再对999801取余数的方法,否则时间和空间上都承受不了。
    可以尝试从以下几个角度考虑:
    1. 高精度计算是肯定需要的,例如n是一个1000位十进制整数,要计算它除以999101的余数,这个代码就必须使用高精度计算。
    2. 数论中一些简单的同余性质,例如,(a * b) % p == ((a % p) * (b % p)) % p(答案似乎没法敲公式,就用代码表达一下吧……),有了这个性质,计算a和b乘积对p取余的值,如果a和b乘积超过了你的存储范围,那就可以把a和b分别对p取余,然后把余数相乘,再对p取余。这样的性质可以辅助你降低时间和空间上的复杂度。
    3. 最后大组合数取模,可以考虑用Lucas定理来计算,这是在组合数取模中相当常用的定理。
    以上是我的一些想法,仅供参考。也期待有大牛能给出更好的解答^_^

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(4条)

报告相同问题?

悬赏问题

  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能
  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
  • ¥50 NT4.0系统 STOP:0X0000007B
  • ¥15 想问一下stata17中这段代码哪里有问题呀
  • ¥15 flink cdc无法实时同步mysql数据
  • ¥100 有人会搭建GPT-J-6B框架吗?有偿