Combinational
| 0.2h | 组合数 | NOIP2011 提高组 计算系数 | 普及 | https://www.luogu.com.cn/problem/P1313 |
|---|---|---|---|---|
| 0.25h | 组合数 | NOIP2016 提高组 组合数问题 | 提高 | https://www.luogu.com.cn/problem/P2822 |
| 0.25h | 乘法原理 | [HNOI2008]越狱 | 提高 | https://www.luogu.com.cn/problem/P3197 |
| 0.5h | 多重排列 | POJ3421 X-factor Chains | 提高 | http://poj.org/problem?id=3421 |
| 1h | 错位排列 | [SDOI2016]排列计数 | 提高 | https://www.luogu.com.cn/problem/P4071 |
| 0.5h | 重复选择问题 | UVa10910 Marks Distribution | 提高 | https://www.luogu.com.cn/problem/UVA10910 |
| 0.5h | 递推计数 | UVA1510 Neon Sign | 提高 | https://www.luogu.com.cn/problem/UVA1510 |
| 1.5h | 容斥原理 | UVa11806 Cheerleaders | 提高+ | https://www.luogu.com.cn/problem/UVA11806 |
| 0.5h | 递推计数 | UVa11401 Triangle Counting | 提高 | https://www.luogu.com.cn/problem/UVA11401 |
| 1h | 二项式系数 | Irrelevant Elements, NEERC 2004 | 提高 | http://bailian.openjudge.cn/practice/2167?lang=en_US |
计算系数¶
#include <cstdio>
using namespace std;
const int N = 1005;
const int mod = 10007;
#define int long long
int c[N][N];
int a, b, k, n, m;
int pow(int x, int y) {
int ans = 1, pas = x;
while (y) {
if (y & 1) ans = ans * pas % mod;
pas = pas * pas % mod;
y >>= 1;
}
return ans;
}
int dfs(int n, int m) {
if (!m) return c[n][m] = 1;
if (m == 1) return c[n][m] = n;
if (c[n][m]) return c[n][m];
if (n - m < m) m = n - m;
return c[n][m] = (dfs(n - 1, m) + dfs(n - 1, m - 1)) % mod;
}
signed main() {
scanf("%lld%lld%lld%lld%lld", &a, &b, &k, &n, &m);
c[1][0] = c[1][1] = 1;
a %= mod, b %= mod;
int ans = 1;
ans = (ans * pow(a, n)) % mod;
ans = (ans * pow(b, m)) % mod;
if (n > m) n = m;
ans = (ans * dfs(k, n)) % mod;
printf("%lld\n", ans);
}组合数问题¶
#include <bits/stdc++.h>
using namespace std;
int t, k, n, m;
const int N = 2005;
int c[N][N], s[N][N];
void prepare() {
// 归纳基础
c[1][1] = 1;
for (int i = 0; i <= 2000; ++i) c[i][0] = 1;
// 递推组合数
for (int i = 2; i <= 2000; ++i) {
for (int j = 1; j <= i; ++j) {
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % k;
}
}
for (int i = 2; i <= 2000; ++i) {
for (int j = 1; j <= i; ++j) {
// 容斥原理，矩阵求和
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
// 如果是整除，答案增加1
if (c[i][j] == 0) s[i][j] += 1;
}
// 向后更新一步
s[i][i + 1] = s[i][i];
}
}
int main() {
cin >> t >> k;
prepare();
while (t--) {
cin >> n >> m;
if (m > n) m = n;
cout << s[n][m] << endl;
}
return 0;
}越狱¶
// 考虑不会发生“越狱”的情况
// 第一个位置有 m 个选择
// 第二个位置有 (m-1) 个选择
// 以后每个位置都有 (m-1) 个选择
// 所以不会“越狱”有 m*(m-1)^(n-1) 种情况
// 一共会有 m^n 种情况
// 答案要求会“越狱”的情况，即 m^n - m*(m-1)^(n-1)
#include <iostream>
using namespace std;
typedef long long ll;
const int MOD = 100003;
ll qexp(ll base, ll power) {
if (power == 0) return 1;
ll half = qexp(base, power / 2);
ll ans = (half * half) % MOD;
if (power & 1) ans = (ans * base) % MOD;
return ans;
}
int main() {
ll m, n;
cin >> m >> n;
cout << (qexp(m, n) - m * qexp(m - 1, n - 1) % MOD + MOD) % MOD << endl;
}X-Factor Chains¶
/**
* @file poj/3421/main.cpp
* @author Ruiming Guo ([email protected])
* @brief
* 输入正整数x，求 x
* 的因子组成的满足任意前一项都能整除后一项的序列的最大长度，
* 以及所有不同序列的个数
*
*
* @version 0.1
* @date 2022-04-29
*
* @copyright Copyright (c) 2022
*
*/
#include <iostream>
using namespace std;
const int N = 22;
typedef unsigned long long ull;
ull factorial[N + 1] = {1};
// 阶乘数组 打表
void init(int n) {
for (int i = 1; i <= n; ++i) factorial[i] = factorial[i - 1] * i;
}
void solve(ull x) {
ull fcount = 0, // x 的因子的数量
denominator = 1; // 分母
for (ull i = 2; i <= x / i; ++i) {
if (x % i == 0) { // i 是 x 的一个因子
int ecount = 0; // 求这个因子的次方数
while (x % i == 0) {
ecount++;
x /= i;
}
// i, i^2, i^3, ..., i^ecount 都是 x 的因子
fcount += ecount;
denominator *= factorial[ecount];
}
}
// 如果 x 不是 1，需要单独统计一次因子 1
// 是 1 的话，fcount应该是 0
if (x != 1) fcount += 1;
cout << fcount << " " // 最大长度
<< factorial[fcount] / denominator // 组合计数，因子个数
<< endl;
}
int main() {
init(N);
ull x;
while (cin >> x) solve(x);
return 0;
}排列计数¶
/**
* @file luogu/4071/main.cpp
* @author Ruiming Guo ([email protected])
* @brief 错位排列问题，f[i] = (i-1)*f[i-1] + (i-1)*f[i-2]
* @version 0.1
* @date 2022-04-29
* @note SDOI 卡常数数正常现象
*
* @copyright Copyright (c) 2022
*
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod = 1e9 + 7;
const int N = 1000010;
ll factorial[N];
ll f[N];
ll qexp(ll a, ll b) {
ll res = 1;
while (b) {
if (b & 1) res *= a, res %= mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
inline ll inv(ll x) { return qexp(x, mod - 2); }
void init() {
factorial[0] = 1;
for (ll i = 1; i < N; ++i) factorial[i] = factorial[i - 1] * i % mod;
f[0] = 1, f[1] = 0, f[2] = 1;
for (ll i = 3; i < N; ++i)
f[i] = ((i - 1) * f[i - 1] % mod + (i - 1) * f[i - 2] % mod) % mod;
}
inline ll C(ll x, ll y) {
return factorial[x] * inv(factorial[x - y]) % mod * inv(factorial[y]) % mod;
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
init();
ll tc;
cin >> tc;
while (tc--) {
ll n, m;
cin >> n >> m;
ll ans = C(n, m) * f[n - m] % mod;
cout << ans << endl;
}
}Marks Distribution¶
/**
* @file uva/10910/main.cpp
* @author Ruiming Guo ([email protected])
* @brief 一个学生选修了 N 门课程，
* 一共得到了 T 分
* 已知他都及格了
* 给出各门课程的及格分数线
* 问该学生可能的成绩组合的种类数
* @version 0.1
* @date 2022-04-29
*
* @copyright Copyright (c) 2022
*
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
int tc;
cin >> tc;
while (tc--) {
ll x, y, z;
cin >> x >> y >> z;
y -= x * z;
ll ans = 0;
if (y >= 0) {
ans = 1;
ll now = y + x - 1 - max(x - 1, y);
ll tot = 1;
for (int i = 1; i <= now; ++i) {
tot *= i;
ans *= (y + x - i);
ll hel = __gcd(tot, ans);
tot /= hel;
ans /= hel;
}
}
cout << ans << endl;
}
}Neon Sign¶
/**
* @file uva/1510/main.cpp
* @author Ruiming Guo ([email protected])
* @brief 给定一个有 n 个顶点的完全图，给定图上各边为红色或蓝色（Beat Saber!）
* 问同种颜色的边构成的三角形的数量
*
* 一共构成的三角形C(n, 3) = n*(n-1)*(n-2)/6
*
* 对一个“不纯”的三角形，一定是其中两条同色一条异色，
* 那么对其三个点，有两个点会出现以每个点为端点的两条边异色的情况，
* 所以只需要统计这种情况（每个点引出的红边数量*该点引出蓝边数量）
* 记录为 sum，
* “不纯”的三角形的个数即为 sum / 2
*
* @version 0.1
* @date 2022-04-29
*
* @copyright Copyright (c) 2022
*
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, sum, t[N][2];
int main() {
int tc;
cin >> tc;
while (tc--) {
memset(t, 0, sizeof(t));
cin >> n;
sum = 0;
for (int i = 1; i <= n - 1; ++i) {
for (int j = i + 1; j <= n; ++j) {
int color;
cin >> color;
++t[i][color];
++t[j][color];
}
}
for (int i = 1; i <= n; ++i) sum += t[i][0] * t[i][1];
printf("%lld\n", 1LL * n * (n - 1) * (n - 2) / 6 - sum / 2);
}
}Cheerleaders¶
/**
* @file uva/11806/main.cpp
* @author Ruiming Guo ([email protected])
* @brief
* @version 0.1
* @date 2022-04-29
* 在一个 n×m 的矩阵中摆放 k 个石子，要求第一行、第一列、第 m 行、第
* n 列必须有石子，求方案总数。T≤50,n≤20,m≤20,k≤500。
*
*
* @copyright Copyright (c) 2022
*
*
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 510, mod = 1e6 + 7;
int T, t, m, n, k, c[N][N], ans;
// 递推法计算组合数
void init() {
c[0][0] = 1;
for (int i = 1; i <= 500; ++i) {
c[i][0] = 1;
for (int j = 1; j <= i; ++j)
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
signed main() {
scanf("%lld", &T);
init();
while (T--) {
scanf("%lld%lld%lld", &m, &n, &k);
ans = 0; // 要往下减多少种情况
// 条件：第一行有石子、第一列有石子、第 m 行有石子、第 n 列有石子
// 枚举状态，第 i 位为 1 表示 i 条件不被满足
for (int S = 0; S < (1 << 4); ++S) {
int x = m, // 可以放棋子的行数
y = n, // 可以放棋子的列数
cnt = 0; // 当前状态下有cnt个条件不被满足
for (int i = 0; i < 4; i++) // 枚举条件
if ((S >> i) & 1) { // 第i个条件未被满足
if (i & 1) //若是条件0或条件2，那么有一行不能放（即x--）
x--;
else //若是条件1或条件3，那么有一列不能放（即y--）
y--;
cnt++; // 未满足的条件数+1
}
if (!cnt) continue; // 都满足了，不往下减
if (cnt & 1)
ans = (ans + c[x * y][k] % mod) % mod;
else
ans = (ans + mod - c[x * y][k] % mod) % mod;
}
// 总方案数减有任意一个条件不被满足的方案数
printf("Case %lld: %lld\n", ++t, (c[n * m][k] % mod - ans + mod) % mod);
}
}Triangle Counting¶
/**
* @file uva/11401/main.cpp
* @author Ruiming Guo ([email protected])
* @brief 给定 n 条边，长度分别为1, 2, 3, ..., n
* 。用其中三条边构成一个三角形，一条边只能使用一次，有多少种不同的方案？
* @version 0.1
* @date 2022-04-29
*
* @copyright Copyright (c) 2022
*
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
long long f[N];
int main() {
for (long long i = 4; i < N; i++) {
f[i] = f[i - 1] + ((i - 1) * (i - 2) / 2 - (i - 1) / 2) / 2;
}
long long n;
while (cin >> n) {
if (n < 3) break;
cout << f[n] << endl;
}
return 0;
}Irrelevant Elements¶
#include <cmath>
#include <cstdio>
#include <cstring>
int m, n, a[1000010], p[1000010], now[1000010], ans[1000010];
int main() {
int i, j, k, x, y, z, tot = 0, cnt = 0;
bool flag;
scanf("%d%d", &n, &m);
x = sqrt(m + 0.5);
for (i = 2; i <= x; i++)
if (m % i == 0) {
a[++tot] = i;
while (m % i == 0) {
m /= i;
p[tot]++;
}
}
if (m > 1) {
a[++tot] = m;
p[tot] = 1;
}
for (i = 1; i < n - 1; i++) {
x = n - i;
y = i;
for (j = 1; j <= tot; j++)
while (x % a[j] == 0) {
x /= a[j];
now[j]++;
}
for (j = 1; j <= tot; j++)
while (y % a[j] == 0) {
y /= a[j];
now[j]--;
}
flag = 1;
for (j = 1; j <= tot; j++)
if (p[j] > now[j]) {
flag = 0;
break;
}
if (flag) ans[++cnt] = i + 1;
}
printf("%d\n", cnt);
for (i = 1; i <= cnt; i++) printf("%d%c", ans[i], i == cnt ? '\n' : ' ');
}
最后更新:
2023-03-28