方格取数
看一眼复杂度,\(O(nm)\)级别的,考虑两个循环的 DP。分析整个题面之后发现,我们穿过边界时,当且仅当另一个连通块的权值比当前的大,否则便不会为了穿过边界而损失当前金块。所以,我们做一个 DP 一样的东西:因为发现每个格子只能走一遍,那么在每一列你只能选择一直向上走和一直向下走,所以这个 DP 便没了后效性,然后再处理连通块之间的连接判断就做完了。
看一眼复杂度,\(O(nm)\)级别的,考虑两个循环的 DP。分析整个题面之后发现,我们穿过边界时,当且仅当另一个连通块的权值比当前的大,否则便不会为了穿过边界而损失当前金块。所以,我们做一个 DP 一样的东西:因为发现每个格子只能走一遍,那么在每一列你只能选择一直向上走和一直向下走,所以这个 DP 便没了后效性,然后再处理连通块之间的连接判断就做完了。
思考量很小的一道题。
先用间接法来算。初始答案为\(n!\),然后考虑容斥掉那些符合排序规则的方案。发现,我们可以分开来考虑,按照容斥的顺序:先考虑只算第一维、第二维的,在加回来两维都考虑的。
第一维和第二维的做法非常显然:排序之后用多重集的排列就行了,考虑每一个相同的区间里面内部乘起来。如果有\(k\)个连续的数段,那么部分的答案就是\(\prod_{i = 1}^l len_k!\)。
这道题很有意思啊。如果暴力枚举,答案式子:
\[ans = \sum_{x}^n \sum_{y}^m {up_{x,y} \choose k} {left_{x,y} \choose k} {right_{x,y} \choose k} {down_{x,y} \choose k}\]
其中\(up, left, right, down\)代表上下左右的常青树棵树。如何降低复杂度?
首先,我们可以考虑进行离散化:上下左右只要有为\(0\)的情况是不可能对答案有贡献的。然后,发现空隙中上下的部分:
这道题需要多重集的知识,如果没有学习请看这篇博客的多重集部分。
很明显,题意要求我们求出多重集的组合数,且为“增强版组合数”。所以,我们根据公式,使用二进制分解的方法来求出即可。这是一道比较裸的多重集组合数问题。
// CF451E.cpp #include <bits/stdc++.h> #define ll long long using namespace std; const int mod = 1e9 + 7, MAX_N = 25; ll arr[MAX_N], n, inv[MAX_N], m; ll quick_power(ll bas, ll tim) { ll ans = 1; while (tim) { if (tim & 1) ans = ans * bas % mod; bas = bas * bas % mod; tim >>= 1; } return ans; } ll C(ll a, ll b) { if (a < 0 || b < 0 || a < b) return 0; a %= mod; if (a == 0 || b == 0) return 1; ll ans = 1; for (int i = 0; i < b; i++) ans = ans * (a - i) % mod; for (int i = 1; i <= b; i++) ans = ans * inv[i] % mod; return ans; } int main() { scanf("%lld%lld", &n, &m); for (int i = 1; i <= n; i++) scanf("%lld", &arr[i]); inv[0] = 1; for (int i = 1; i < MAX_N; i++) inv[i] = quick_power(i, mod - 2); ll ans = 0; for (int stat = 0; stat < (1 << n); stat++) if (stat == 0) ans = (ans + C(n + m - 1, n - 1)) % mod; else { ll t = n + m, p = 0; for (int i = 0; i < n; i++) if ((stat >> i) & 1) p++, t -= arr[i + 1]; t -= (p + 1); if (p & 1) ans = (ans - C(t, n - 1)) % mod; else ans = (ans + C(t, n - 1)) % mod; } ans = (ans + mod) % mod; printf("%lld", ans); return 0; }
source:Page 172,《算法竞赛进阶指南》李煜东著