Genral
惊险刺激。但还是菜。
统计：
| 得分 | 得分率 | 挂分率 | AC 数 |
|---|---|---|---|
| 200 | 50% | 0% | 2 |
各题目详情：
| 题目 | A | B | C | D | Total |
|---|---|---|---|---|---|
| 期望得分 | 100 | 0 | 100 | 0 | 200 |
| 实际得分 | 100 | 0 | 100 | 0 | 200 |
| 挂分 | 0 | 0 | 0 | 0 | 0 |
A
\(n≤4\)？直接搜！
于是就没了 60。
显然这玩意应该 DP 啊，设 dp[i][j][k][l] 为四个桶耐久分别剩多少的概率，然后循环即可。
B
DP。
想了个三维 DP，算出来发现爆空间了，于是开 float 挂了两个点。（离谱：开成 double 占约 420MB，OJ 上居然能过）
区间 DP，设 dp[i][j] 为前 i 个数划分为 j 段时最大的特殊值之和。转移时枚举区间的起点即可。
C
广义矩阵乘法：用矩阵快速幂计算满足结合律的运算。
一波 Floyd 算出最短路线的矩阵，接着可以按照题意算出移动概率的矩阵，然后快速幂即可。
我不会写 Floyd，更想不到矩阵快速幂，于是 0 分。
D
不是为啥输样例有 30 啊……
首先可以考虑暴力的做法。
开一个 \((n+1)\times k\) 的数组，f[i][j] 表示第 \(i\) 个骡子拉不拉第 \(j\) 个货。往每个格子里填 0/1 爆搜+判断即可。
很明显判断的时候要求：
- 没有一列的 0~n-1 行全为 1；
- 至少一列的 1~n 行全为 0。
于是考虑枚举中间的 1~n-1 行有 i 列为 0，j 列全为 1，这部分答案就有了：
\[\sum_{i=1}^k \sum_{j=0}^{k-i} C_k^i C_{k-1}^j (2^{n-1}-2)^{k-i-j}
\]
其中最后一项就是长度为 \(n-1\) 的 01 串情况数的列数次方。
接着考虑剩下的两行：
- 第 0 行，很明显除了 1~n-1 位置全是 1 的列填 0 之外都随便填，于是答案乘上 \(2^{k-j}\)。
- 第 n 行，因为 1~n 行至少有一列全为 0，所以全 0 列不要全填 1，别的列随便。答案乘 \(2^{k-i}(2^i-1)\)。
但是这样多少有点慢，因为 \(n,k \le 10^{18}\)，所以我们需要让它只出现在幂指数（快速幂）及常数上。
换个顺序，它就变成了：
\[2^k\sum_{i=1}^k C_k^i(2^i-1) \sum_{j=0}^{k-i} C_{k-1}^j (2^{n-1}-2)^{k-i-j}2^{k-i-j}
\]
最右边给他合并一下，再给 1 来个指数：
\[2^k\sum_{i=1}^k C_k^i(2^i-1) \sum_{j=0}^{k-i} C_{k-1}^j (4^{n-1}-4)^{k-i-j}1^j
\]
然后一波二项式定理，就是：
\[2^k\sum_{i=1}^k C_k^i(2^i-1)(2^n-3)^{k-i}
\]
把 \((2^i-1)\) 这一项拆开：
\[2^k\left[\sum_{i=1}^k C_k^i(2^n-3)^{k-i}2^i-\sum_{i=1}^k C_k^i(2^n-3)^{k-i}\right]
\]
二项式定理展开（注意补上第 0 项），整理一下：
\[2^k\left[(2^n-1)^k-(2^n-2)^k\right]
\]
然后快速幂，就结束了。