2020-2021:teams:alchemist:weekly_digest_8
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:weekly_digest_8 [2020/07/31 11:30] hardict [龙鹏宇 Hardict] |
2020-2021:teams:alchemist:weekly_digest_8 [2020/07/31 11:43] (当前版本) hardict [龙鹏宇 Hardict] |
||
|---|---|---|---|
| 行 82: | 行 82: | ||
| === 来源： === | === 来源： === | ||
| - | 51nod 1778 | + | [[http://acm.hdu.edu.cn/showproblem.php?pid=6333|HDU 6333]] |
| - | + | ||
| - | https://www.51nod.com/Challenge/Problem.html#problemId=1778 | + | |
| === 标签： === | === 标签： === | ||
| + | |||
| + | 分块 组合 | ||
| === 题意： === | === 题意： === | ||
| + | |||
| + | 求解$T\leq 10^5$组$\sum_{i=0}^{m}C_{n}^{i}$ | ||
| + | |||
| + | $1\leq n,m\leq 10^5$ | ||
| === 题解： === | === 题解： === | ||
| + | |||
| + | $pre[n][m]=\sum_{i=0}^m C_n^i$ | ||
| + | |||
| + | $pre[n][m]=pre[n][m-1]+C_n^m,pre[n][m]=\sum_{i=0}^m (C_{n-1}^i+C_{n-1}^{i-1})=2pre[n-1][m]-C_{n-1}^i$ | ||
| + | |||
| + | 于是得到了$(n,m)$对于$(n \pm 1,m),(n,m \pm 1)$的转移 | ||
| + | |||
| + | 利用莫队将询问分块对$(n,m)$进行转移，即可解决题目 | ||
| === 评论： === | === 评论： === | ||
| + | |||
| + | 一开始一组想对前缀和推一个公式 | ||
| + | |||
| + | 后面注意到数据范围才考虑是否可以利用暴力转移分块解决题目 | ||
| + | |||
| + | 对于这种状态可以在相邻位快速转移的问题可以根据数据范围考虑是否分块 | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
2020-2021/teams/alchemist/weekly_digest_8.1596166233.txt.gz · 最后更改: 2020/07/31 11:30 由 hardict
