先放一张图片，内容还没写完，不断补全吧。需要注意的是其中很多内容、代码并未经过验证，如有疏漏请指出，谢谢。 转载请注明出处：http://blog.csdn.net/zhengly123

问题：

求

方法一：组合数公式

最直接的方法，求取模即可。

方法二：组合数递推公式

利用公式

方法三：高精度求组合数

此方法较少用到，实现难度大，所以如果你的代码能力特别好可以试着写。

方法四：分解质因数

利用欧拉线性筛我们可以求得一个数是否是质数，同时可以求得一个合数的最小质因数，所以我们可以将n！进行分解质因数，用数组cnt记录n！中出现某个因子的个数，从大往小遇到合数则分解为两个数的乘积，加入这个两个因子中。对分子分母都进行一次，然后相减，最终得到一个质数的幂的乘积。对于每一个幂我们用高精度能在内求解，而由质数定理，小于n的质数有个，所以总的时间复杂度为O（n）。 方法四代码：未经测试，不保证正确性 #include #include #include #include #include #include #define MEM(a) memset(a,0,sizeof(a)) using namespace std; typedef long long ll; const int INF = 999999999; const int MAXN = 100000; bool check[MAXN]; int prime[MAXN], cnt, minn[MAXN];//minn储存最小的质因子 void prime_calc(int n)//线性筛 { int i, j; for (i = 2; i <= n; ++i) { if (!check[i]) prime[++cnt] = i; for (j = 1; j <= cnt; ++j) { if (i*prime[j] > n) break; check[i*prime[j]] = 1; minn[i*prime[j]] = prime[j]; if (i%prime[j] == 0) break; } } } int num[MAXN], num2[MAXN]; int pow(int a, int b, int c)//快速幂 { int ans = 1; a %= c; for (; b; b >>= 1) { if (b & 1) ans = (ans*a) % c; a = a*a%c; } return ans; } void work() { int i, j, n, m, d, ans = 1; scanf("%d%d%d", &n, &m, &d); prime_calc(n); for (i = n; i >= 2; --i) { if (i > m) ++num[i]; if (check[i]) { num[minn[i]] += num[i]; num[i / minn[i]] += num[i]; num[i] = 0; } } for (i = n - m; i >= 2; --i) { ++num2[i]; if (check[i]) { num2[minn[i]] += num2[i]; num2[i / minn[i]] += num2[i]; num2[i] = 0; } } for (i = 2; i <= n; ++i) { num[i] -= num2[i]; ans = (ans*pow(i, num[i], d)) % d; } printf("%d ", ans); } int main() { work(); return 0; }