問題來源：
HUST07校賽
原題見：
http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1338
提交方式：
WOJ1338問題描述：
對于N（1<=N<=80)個(gè)數(shù)A[1...N](1<=A[i]<=500)，他們的和為sum，求sum!/(A[1]!*A[2]!*...*A[N]!)%40009。
解題過程：
對于這個(gè)題目，我當(dāng)時(shí)就推出了上面的公式，然后就卡了，不知道后面怎么辦——這些數(shù)可是非常大。
其實(shí)這個(gè)問題的重點(diǎn)就在于運(yùn)用擴(kuò)展歐幾里德（感謝Felicia的指導(dǎo)）：
對于 a/b%m = ans, 求 ans。
a = a%m, b = b%m
ans = (a % m)*(x % m) % m （x為b的逆元）
求逆元?jiǎng)t利用擴(kuò)展歐幾里德：
對于 b*x = 1(mod m)
可以求b*x + m*y = 1的解（ 用extennd_Euclid(b, m, x, y) )!
然后把 x 映射到 [0,m)區(qū)間，帶入上式， 即得解。附代碼：
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 閱讀(2564)
評論(5) 編輯 收藏 引用 所屬分類:
Problem Solving 、
Pure Theory 、
Memo