Tony102's Blog - 组合计数
type: channel
link: https://tony102.com/index.php/tag/%E7%BB%84%E5%90%88%E8%AE%A1%E6%95%B0/
items: CF1228E Another Filling the Grid
items: Luogu6076 [JSOI2015]染色问题
items: Luogu1641 [SCOI2010]生成字符串
items: CF1081C Colorful Bricks

CF1228E Another Filling the Grid
type: item
date: 2021-10-07T19:55:00+08:00
description: LinkSol容斥练习题。其实跟 【JSOI2015】染色问题 差不多，异曲同工之妙。可以先看看那道题。枚举有多少行没有填 $1$，假设有 $i$ 行，那么这 $i$ 行填数字的方案数是 $(k-1)^i$，剩余 $n-i$ 行的填数字的方案数是 $k^{n-i}$。此外，还应减去全部都没填 $1$ 的方案数：$(k-1)^n$。这一类题目有一个共同的性质，也是可以像上述那样计算的基础：行和列之间独立。我们刚才那样是填一行的，$n$ 行全填只需要 $n$ 次幂即可。所以：$$ Ans = \sum\limits_{i=0}^{n} (-1)^i \binom{n}{i} ((k-1)^i \cdot k^{n-i} - (k-1)^n)^n $$可以在 $O(n \log n)$ 内的时间计算完。Code#include <bits/stdc++.h> #define int long long using namespace std; const int N = 2.5e2, SIZE = N + 5; const int mod = 1e9 + 7; int n, k; int fac[SIZE], inv[SIZE], pw[SIZE], pw1[SIZE]; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch(); return b ? a : -a; } } using GTR::read; int qPow(int a, int b) { int ans = 1ll; for ( ; b; b >>= 1, a = a * a % mod) { if (b & 1) ans = ans * a % mod; } return ans % mod; } void init() { fac[0] = pw[0] = pw1[0] = 1ll; for (int i = 1; i <= N; ++ i) fac[i] = fac[i - 1] * i % mod, pw[i] = pw[i - 1] * k % mod, pw1[i] = pw1[i - 1] * (k - 1) % mod; inv[N] = qPow(fac[N], mod - 2ll); for (int i = N - 1; ~i; -- i) inv[i] = inv[i + 1] * (i + 1) % mod; } int C(int x, int y) { if (x < y) return 0ll; return fac[x] * inv[y] % mod * inv[x - y] % mod; } signed main() { n = read(), k = read(); init(); int ans = 0; for (int i = 0; i <= n; ++ i) { int p = qPow(((pw1[i] * pw[n - i] % mod) - pw1[n] + mod) % mod, n) % mod; if (i & 1) ans = (ans - (C(n, i) * p % mod) + mod) % mod; else ans = (ans + (C(n, i) * p % mod)) % mod; } printf("%lld\n", ans); return 0; }

Luogu6076 [JSOI2015]染色问题
type: item
date: 2021-10-07T19:45:00+08:00
description: LinkSol没有理解好这道题目，重新落实。第一步就是要认识到，行和列可以分开计算。这道题有两个限制，一个是每种颜色至少要出现一次，而一个就是每一行和每一列都要保证有格子染色。先来处理第一个限制：颜色。我们设 $f_i$ 表示只用了 $i$ 中颜色、并且满足行和列染色限制的方案数。我们知道：$$ Ans = \sum\limits_{i=0}^{c} (-1)^{i} \binom{c}{i} f_{c-i} $$含义：从 $c$ 中选 $i$ 种颜色， 乘上只选 $c-i$ 的方案数，容斥系数：$(-1)^i$现在我们来考虑怎么求 $f_i$。我们知道 $n^{k}$ 的组合意义是将 $k$ 个小球放入 $n$ 个有区别的盒子中。那么我们可以认为每种盒子的颜色不同，每个小球上标了列标。所以总的给这一列染色（可以不染）的方案数为 $(i+1)^m$，$(i+1)$ 是因为可以不染（可以认为没染颜色是一种颜色）。因为一全空为非法，所以减 $1$ 后再进行 $n$ 次幂（有 $n$ 行，因为行之间独立）。现在我们枚举选了多少列涂色，类似地计算：$$ f_i = \sum\limits_{k=0}^{m} (-1)^k \binom{m}{k} ((i+1)^k-1)^n $$$O(n \log n)$ 计算即可。Code#include <bits/stdc++.h> #define int long long using namespace std; const int SIZE = 4e2 + 5; const int mod = 1e9 + 7; int n, m, c; int inv[SIZE], fac[SIZE], f[SIZE]; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch(); return b ? a : -a; } } using GTR::read; int qPow(int a, int b) { int ans = 1ll; for ( ; b; b >>= 1, a = a * a % mod) { if (b & 1) ans = ans * a % mod; } return ans % mod; } void init() { const int N = 4e2; fac[0] = 1ll; for (int i = 1; i <= N; ++ i) fac[i] = fac[i - 1] * i % mod; inv[N] = qPow(fac[N], mod - 2ll); for (int i = N - 1; ~i; -- i) inv[i] = inv[i + 1] * (i + 1) % mod; } int C(int x, int y) { if (x < y) return 0ll; return fac[x] * inv[y] % mod * inv[x - y] % mod; } signed main() { n = read(), m = read(), c = read(); init(); for (int i = 1; i <= c; ++ i) { f[i] = (qPow(i + 1, m) - 1ll + mod) % mod, f[i] = qPow(f[i], n) % mod; int res = 0; for (int k = 1; k <= m; ++ k) { int pw = (qPow(i + 1, m - k) - 1ll + mod) % mod; pw = qPow(pw, n) % mod; if ((k - 1) & 1) res = (res - (pw * C(m, k) % mod) + mod) % mod; else res = (res + (pw * C(m, k) % mod)) % mod; } f[i] = (f[i] - …

Luogu1641 [SCOI2010]生成字符串
type: item
date: 2021-06-12T14:31:00+08:00
description: LinkSol这个题的方法对于一类恰好要求某个有顺序的值到达一个阀值的限制的题目是启发的用 $x$ 轴的 $+1$ 表示 $1$ 的数量与 $0$ 的数量的和 $+1$, $y$ 轴方向的 $+1$ 表示 $1$ 的数量与 $0$ 的数量的差 $+1$. 那么最终要求的放置的 $n$ 个 $1$ 和 $m$ 个 $0$ 就会停在图中的 $L(n + m, n - m)$ 这个点上.从 $0$ 走到 $L(n+m,n-m)$ 的方案数可以被表示为 $\binom{n + m}{n} = \binom{n+m}{m}$ , 组合意义阐释: 我们一共要选出 $n + m$ 个 $0$ 或 $1$ , 也就是在图中走了 $n + m$ 步, 其中有 $n$ 步选了 $1$ , 就代表在图中从 $(x, y)\to (x + 1, y+1)$ ,也就是 $1$ 与 $0$ 数量的差 $+1$, 选 $0$ 则是 $(x,y) \to (x +1,y-1)$ ,就是往 $\searrow$ 方向上走了一步. 那么走到 $L(n+m,n-m)$ 这个点的方案数就是在 $n+m$ 步里面选了 $n$ 步往 $\nearrow$ 或者 $m$ 步 $\searrow$那么再来考虑题目给的限制.题目的限制其实就是任意一个前缀一定要满足当前在图上的纵坐标要不经过 $y = -1$ 这一条线.这种经过一条直线且起点终点不在一边的都有一个方法,就是把它关于那条直线对称一下就好了对称了之后七点到了 $(0,-2)$ ,那么从 $(0,-2)$ 走到 $(n+m,n-m)$ 这个点的方案数就是$\binom{n+m}{m-1}$用总的方案数减掉这部分不合法的就可以了Code#include <bits/stdc++.h> #define int long long using namespace std; const int SIZE = 2e6 + 5; const int mod = 20100403; int n, m; int inv[SIZE], fac[SIZE]; namespace GTR { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (c < 48 || c > 57) b ^= c == '-', c = fetch(); while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch(); return b ? a : -a; } } using GTR::read; int qPow(int a, int b) { int ans = 1ll; for ( ; b; b >>= 1, a = a * a % mod) { if (b & 1) ans = ans * a % mod; } return ans % mod; } void init() { const int siz = n + m; fac[0] = fac[1] = 1ll; for (int i = 2; i <= siz; ++ i) fac[i] = fac[i - 1] * i % mod; inv[siz] = qPow(fac[siz], mod - 2ll); for (int i = siz - 1; ~i; -- i) inv[i] = inv[i + 1] * (i + 1ll) % mod; } int C(int x, int y) { return x < y ? 0ll : fac[x] * inv[y] % mod * inv[x - y] % mod; } signed main() { // freopen("code.in", "r", stdin); n = read(), m = read(); init(); printf("%lld\n", (C(n + m, m) - C(n + m, m - 1) + mod) % mod); return 0; }

CF1081C Colorful Bricks
type: item
date: 2020-11-14T21:42:00+08:00
description: LinkSol这种跟旁边的的东西有限制的题目通常可以用插板法做相当于现在我要插$k$块板子进去，现在这一排砖被分成了$k+1$段现在钦定有第一块板子右边那块砖的颜色，有 $m$ 种选择。那么剩下的 $k-1$ 块板子右边的都可以涂 $m-1$ 种颜色，就有$(m-1)^k$ 种方案。同时保证板子左边和右边的颜色不同。现在的问题是，要在这$n$块砖中选择一些位置插板子，因为 $n$ 个球只有 $n-1$ 个位置，所以有 $\binom{n-1}{k}$ 种方案。根据乘法原理可得最后的答案是：$$\binom{n-1}{k}\times m(m-1)^k$$Code#include <bits/stdc++.h> using namespace std; #define int long long const int SIZE = 2e3 + 5; const int mod = 998244353; int n, m, k; int fac[SIZE], inv[SIZE]; namespace ae86 { const int bufl = 1 << 15; char buf[bufl], *s = buf, *t = buf; inline int fetch() { if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; } return *s++; } inline int read() { int a = 0, b = 1, c = fetch(); while (!isdigit(c))b ^= c == '-', c = fetch(); while (isdigit(c)) a = a * 10 + c - 48, c = fetch(); return b ? a : -a; } } using ae86::read; inline int qPow(int a, int b) { int ans = 1; while (b) { if (b & 1) ans = ans * a % mod; b >>= 1, a = a * a % mod; } return ans % mod; } inline void init() { fac[0] = 1; for (int i = 1; i <= 2000; ++ i) fac[i] = fac[i - 1] * i % mod; inv[2000] = qPow(fac[2000], mod - 2) % mod; for (int i = 1999; i >= 0; -- i) inv[i] = inv[i + 1] * (i + 1) % mod; } inline int C(int x, int y) { if (y == 0) return 1; return ((fac[x] % mod) * (inv[y] * inv[x - y] % mod) % mod); } signed main() { init(); n = read(), m = read(), k = read(); if (!k) { int ans = m * qPow(m - 1, k) % mod; printf("%lld\n", ans % mod); } else { int ans = C(n - 1, k) * m % mod * qPow(m - 1, k) % mod; printf("%lld\n", ans); } return 0; }