2 rl529014 rl529014 于 2016.03.16 21:58 提问

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

图片说明

问题描述
  输入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
应该要注册才能用吧,谢谢各位大牛了。

4个回答

cxsmarkchan
cxsmarkchan   2016.03.16 23: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定理来计算,这是在组合数取模中相当常用的定理。
以上是我的一些想法,仅供参考。也期待有大牛能给出更好的解答^_^

rl529014
rl529014 谢谢你的仔细回答,非常感谢你,今天我把高精度数加减法搞清楚了,明天接着做这个题,应该没问题了。
一年多之前 回复
lm_whales
lm_whales   Rxr 2016.03.17 01:54

组合数可以通过差分(也就是只需要加法)计算
对加法可以取没取模运算使之不出现数据溢出

rl529014
rl529014 恩恩,我明白了一点,谢谢你的回答,非常感谢你
一年多之前 回复
rl529014
rl529014   2016.03.16 22:05

时间有点紧迫,急着回寝室,没描述清楚,实在不好意思

lm_whales
lm_whales   Rxr 2016.03.17 01:58

C(M-1,N-1)+C(M-1,N)=C(M,N)

lm_whales
lm_whales S(K=N,M)C(K-1,N-1)=C(M,N) (M》=N)
一年多之前 回复
lm_whales
lm_whales 可以通过这种公式计算
一年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!