求组合数(取模)的两种方法
两种公式配合Lucas定理使用更佳
Pascal公式打表
由Pascal公式,可知
\[\begin{cases}C_n^k=C_{n-1}^{k-1}+C_{n-1}^k\\C_n^0=C_n^n=1\end{cases}
\]
\]
取二维数组 \(tC[][]\) ,初始化 \(tC[0][0] = 1\); 打表即可。代码最简单,如下:
const int maxn(1005), mod(100003);
int tC[maxn][maxn]; //tC 表示 table of C
inline int C(int n, int k)
{
if(k > n) return 0;
return tC[n][k];
}
void calcC(int n)
{
for(int i = 0; i < n; i++)
{
tC[i][0] = 1;
for(int j = 1; j < i; j++)
tC[i][j] = (C(i - 1, j - 1) + C(i - 1, j)) % mod;
tC[i][i] = 1;
}
}
计算 \(C_n^k\) 返回内联函数 \(C_n^k\) 的值即可。
当然我们知道 \(C_n^k=C_n^{n−k}\),所以上面的代码有很多空间和时间的浪费。可以将 \(tC[][]\) 二维数组转化为一维数组存储,同时,当 \(j>i/2\) 时终止第二层循环,新代码如下:
const int maxn(10005), mod(100003);
int tC[maxn * maxn]; //tC 表示 table of C
inline int loc(int n, int k) // C(n, k)返回在一维数组中的位置
{
int locate = (1 + (n >> 1)) * (n >> 1); // (n >> 1) 等价于 (n / 2)
locate += k;
locate += (n & 1) ? (n + 1) >> 1 : 0; // (n & 1) 判断n是否为奇数
return locate;
}
inline int C(int n, int k)
{
if(k > n) return 0;
k = min(n - k, k);
return tC[loc(n, k)];
}
void calcC(int n)
{
for(int i = 0; i < n; i++)
{
tC[loc(i, 0)] = 1;
for(int j = 1, e = i >> 1; j <= e; j++)
tC[loc(i, j)] = (C(i - 1, j) + C(i - 1, j - 1)) % mod;
}
}
显然,由于空间的限制,pascal打表的方式并不适合求取一些比较大的组合数。
所以第二种出现了
逆元法
因为 \(C_n^m=\dfrac{n!}{m!(n-m!)}\) ,所以可以预处理1到n的阶乘对mod取模的结果,然后用“拓展欧几里得算法”或“费马小定理”或“欧拉定理”求 \(m!\) 和 \(n!\) 的逆元,然后相乘即可(乘的过程中记得取模)
原文链接: https://www.cnblogs.com/jasony/p/13377340.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/200802
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!