今天我刷题了吗
搜索文档…
组合数

Pascal 公式打表组合数取模

1
const int maxn = 1e3 + 5;
2
const int mod = 1e5 + 3;
3
int tC[maxn][maxn];
4
5
inline int C(int n, int k)
6
{
7
if (k > n) return 0;
8
return tC[n][k];
9
}
10
11
void calcC(int n)
12
{
13
for (int i = 0; i < n; i++) {
14
tC[i][0] = 1;
15
for (int j = 1; j < i; j++) {
16
tC[i][j] = (C(i - 1, j - 1) + C(i - 1, j)) % mod;
17
}
18
tC[i][i] = 1;
19
}
20
}
Copied!
1
const int maxn = 1e3 + 5;
2
const int mod = 1e5 + 3;
3
int tC[maxn * maxn];
4
5
inline int loc(int n, int k)
6
{
7
int pos = (1 + (n >> 1)) * (n >> 1);
8
pos += k;
9
pos += (n & 1) ? (n + 1) >> 1 : 0;
10
return pos;
11
}
12
13
inline int C(int n, int k)
14
{
15
if (k > n) return 0;
16
k = min(n - k, k);
17
return tC[loc(n, k)];
18
}
19
20
void calcC(int n)
21
{
22
for (int i = 0; i < n; i++) {
23
tC[loc(i, 0)] = 1;
24
for (int j = 1, e = i >> 1; j <= e; j++) {
25
tC[loc(i, j)] = C(i - 1, j) + C(i - 1, j - 1);
26
}
27
}
28
}
Copied!

逆元求组合数取模

最近更新 1yr ago
复制链接