问题来源：
HUST07校赛
原题见：
http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1338
提交方式：
WOJ1338问题描述：
对于N（1<=N<=80)个数A[1...N](1<=A[i]<=500)，他们的和为sum，求sum!/(A[1]!*A[2]!*...*A[N]!)%40009。
解题过程：
对于这个题目，我当时就推出了上面的公式，然后就卡了，不知道后面怎么办——这些数可是非常大。
其实这个问题的重点就在于运用扩展欧几里德（感谢Felicia的指导）：
对于 a/b%m = ans, 求 ans。
a = a%m, b = b%m
ans = (a % m)*(x % m) % m （x为b的逆元）
求逆元则利用扩展欧几里德：
对于 b*x = 1(mod m)
可以求b*x + m*y = 1的解（ 用extennd_Euclid(b, m, x, y) )!
然后把 x 映射到 [0,m)区间，带入上式， 即得解。附代码：
1
2 int extend_Euclid(int a, int b, int &x, int &y)
3 {
4 if (b == 0)
5 {
6 x = 1;
7 y = 0;
8 return a;
9 }
10 else
11 {
12 int ans = extend_Euclid(b, a % b, x, y); /////
13 int t = x;
14 x = y;
15 y = t - (a / b) * y;
16 return ans;
17 }
18 }
19
20
posted on 2008-03-14 16:46
R2 阅读(2575)
评论(5) 编辑 收藏 引用 所属分类:
Problem Solving 、
Pure Theory 、
Memo