摘要：
题意 有 \(a\) 和 \(b\) 两个长度为 \(n\) 的序列，其中元素两两配对， \(a>b\) 的配对需比 \(a<b\) 的配对多恰好 \(k\) 个，求方案数 Solution 我们设 \(f_{i,j}\) 为前 \(i\) 个 \(a\) 中，选了 \(j\) 组 \(a>b\) 阅读全文
posted @ 2020-09-09 21:14
jasony_sam
阅读(121)
评论(0)
推荐(0)
摘要：
Solution 设 \(f[i][j][k]\) 表示一辆每公里耗油量为 $1$ 的货车从 \(i\) 到 \(j\) 中途加 \(k\) 次油最小的油箱容量。枚举起点 \(st\) 和加油的次数 \(k\) ，这样就固定了两维，显然有DP方程： \[ f[i][j][k]=\min\limits 阅读全文
posted @ 2020-09-09 20:16
jasony_sam
阅读(105)
评论(0)
推荐(0)
摘要：
Solution 原题最后的答案比较难求，所以我们可以反方向思考：只需要求出所有人生日不同的概率。 显然这个概率为 \(\dfrac{A_{2^n}^m}{2^{nm}}=\dfrac{\prod_{i=2^n-m+1}^{2^n-1}}{2^{n(m-1)}}\) 。 分母部分用快速幂即可，而分子 阅读全文
posted @ 2020-09-09 20:15
jasony_sam
阅读(147)
评论(0)
推荐(0)
浙公网安备 33010602011771号