Solution -「2021.11.27」\Infty
T1.
显然往 \(x < 0, y < 0\) 的点走一定不优。
根据转移式可发现 \(C(x, y)\) 即从 \((0, 0)\) 走到 \((x, y)\) 的方案数 \(\dbinom {x + y} {x}\)。
那么兜一个圈圈再回到目的地显然没有直接往目的地走优。
于是我们可以强化限制:每一步只能向右或者上走。
设 \(f_{i, j}\) 表示走到 \((i, j)\) 的体力的最小花费,则有 \(f(i, j) = \min \{f(i - 1, j), f(i, j - 1)\} + \dbinom {i + j} {j}\)。
其中 \(0 \leq i \leq n, 0 \leq j \leq m\),且 \(f(i, 0) = i, f(0, j) = j\)。
从 \((n, m)\) 点往前倒推转移过程,不难发现走 \((0, 0) \to (0, m) \to (n, m)\) 或者 \((0, 0) \to (n, 0) \to (n, m)\) 一定最短。更确切的:
- 若 \(n = \max \{n, m\},m = \min \{n, m\}\),则 \((0, 0) \to (n, 0) \to (n, m)\) 最短。
- 若 \(m = \max \{n, m\},n = \min \{n, m\}\),则 \((0, 0) \to (0, m) \to (n, m)\) 最短。
考虑直接写出最后答案的柿子,以第一种情况为例。
容易得出 \(\mathbb{Ans} = n + 1 + {\large \sum \limits _{i = 1}^{m}} \dbinom {n + i} {n}\)。
可化为 \(n + 1 + {\large \sum \limits _{i = n + 1}^{m + n}} \dbinom {i} {n} = n + 1 + {\large \sum \limits _{i = 0}^{m + n}} \dbinom {i} {n} - {\large \sum \limits _{i = 0}^{n}} \dbinom {i} {n}\)。
前面一个和式使用变上项求和公式,后一个本来就等于 \(0\),故有:\(\mathbb{Ans} = n + 1 + \dbinom {m + n + 1} {n + 1}\)。
\(m, n\) 很大,但 \(mn \leq 10^{12}\),故考虑利用 \(\dbinom {m + n + 1} {n + 1} = \dbinom {m + n + 1} {m}\),调整计算过程,大力算即可,大概是根号级别的。
T2.
把题目在手上 Rua 一 Rua,你会发现它就是一个有可重复元素的康拓展开(本质上就是一堆 \([0, 9]\) 的数,可重,在全排列中有多少的排列的字典序小于给定排列)。
那就像康托展开一样去玩它。
设原数,即原序列为 \(A\),长度为 \(n\)。对于第 \(i\) 个位置考虑对实际填数方案分类。
- \(i\) 之前的数均与 \(A\) 中对应元素相等,且 \(i\) 上填比 \(A_i\) 小的数。那么 \(i\) 以后的就是没用过的数的排列个数,注意是可重排列。
- \(i\) 及以前的数均与 \(A\) 中对应元素相等。标记当前元素被用过直接往后继续算即可。
仅有以上两种情况,给个部分代码供参考。
for(int i = 1; i <= len; i++) {
for(int j = 0; j < (s[i] - '0'); j++)
if(cnt[j]) {
cnt[j]--;
ans += calc(len - i); // 可重排列
cnt[j]++;
}
cnt[s[i] - '0']--;
}
然后考虑处理这个可重排列。
设需要排列的可重集为 \(B = \{B_1 \times n_1, B_2 \times n_2 , \dots , B_k \times n_k\}\),表示 \(B_i\) 有 \(n_i\) 个。
朴素的排列计算方式为:\(\dfrac {S!} {\prod \limits_{i = 1}^{k}(n_i!)}\),其中 \(S = {\large \sum \limits _{i = 1}^k} n_i\)。
但此题无取模,这样算会炸,考虑换一个方案,我们可以将 \(B_1\) 到 \(B_k\) 按顺序分配到 \(n\) 个位置上。
则排列数可化为:\({\large \sum \limits _{i = 1} ^{k}} \dbinom {n - \mathrm{Pre}(i)} {n_i}\),当中 \(\mathrm{Pre}(i) = {\large \sum \limits _{j = 1} ^{i}} n_j\)。
这样就可以杨辉三角预处理,然后再做了。
T3.
简单容斥。
抬手先判一个若 \((n - 1) \times m < k\),则无解。
接下来发现,如果没有 \([0, n)\) 的限制,利用插板法可答案为 \(\dbinom {m + k - 1} {m - 1}\)。显然这里面会有单个元素超过 \(n - 1\) 的分配方案,考虑去除掉它们。
设至少有 \(x\) 个元素超过了 \(n - 1\) 的方案数为 \(f(x)\),发现 \(f(x) = \dbinom {m} {i} \times \dbinom {m + k - x \times n - 1} {m - 1}\)。
即将这 \(x\) 个元素先每一个都分配 \(n\),在把剩下的分配随便分配的方案数,注意每个元素是不同的,需要考虑顺序。
接下来就容斥呗。可知 \(\mathbb{Ans} = {\large \sum \limits _{i = 0}^{m}f(i) \times k(i)}\),其中 \(k(i) = \left \{ \begin{matrix} -1, x\equiv 1 \pmod 2 \\ 1, x \equiv 0\pmod 2 \end{matrix} \right.\)。
T4.
为什么要难度降序啊。
设至少有 \(x\) 个爱好相同的人的对数为 \(f(x)\)。
则 \(\mathbb{Ans} = {\large \sum \limits _{i = 0}^{5}f(i) \times k(i)}\),其中 \(k(i) = \left \{ \begin{matrix} -1, x\equiv 1 \pmod 2 \\ 1, x \equiv 0\pmod 2 \end{matrix} \right.\)。
\(f(x)\) 可以直接 Trie 或者 Hash + map 统计出来嘛。
就是说,你用 \(O(2^5)\) 对于每一个人去枚举至少那些爱好属于相同的,然后分开计算贡献。
Conclusion.
首先死在了难度降序。
然后死在了 T1 降智打了 Lucas。
接着死在了 T2 对康拓展开毫无印象。
又死在了 T3 手推降智 \(O(nm)\) 容斥。
最后死在了 T4 的失智。
综合来讲,死在了对题目 Trick 的极低的敏感度。
最新文章
- 消除类游戏(js版)
- 线程的Alertable与User APC
- Fiddler
- WebForm复杂控件
- html基本标签结构
- 解决Ubuntu下 Could NOT find CURL (missing: CURL_LIBRARY CURL_INCLUDE_DIR)
- IOS7新特性 edgesForExtendedLayout
- homework-05 大家一起玩游戏~
- VennDiagram 画文氏图/维恩图/Venn
- INDEX FAST FULL SCAN和INDEX FULL SCAN
- linux环境ubuntu: pushd: not found
- grep[行号&;正则匹配字符有颜色]
- 私人订制——属于你自己的Linux
- [UWP] Custom Capability的使用
- HBase 索引创建
- jquery.amaran jquery提示类使用
- urlconnection代码
- BP算法基本原理推导----《机器学习》笔记
- leetcode — sort-colors
- C#WinForm窗体内Panel容器中嵌入子窗体、程序主窗体设计例子