2020-2021:teams:hotpot:2020nowcoder8
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:2020nowcoder8 [2020/08/07 16:04] lotk |
2020-2021:teams:hotpot:2020nowcoder8 [2020/08/07 16:37] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 55: | 行 55: | ||
| ===题解=== | ===题解=== | ||
| - | ====E - ==== | + | ====E - Enigmatic Partition==== |
| - | ===solved by === | + | ===solved by gyp=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 定义n的一种划分为一个不减数列，相邻两项最多差1，首项和末项差2。f(n)为n的划分种数。求T组数据，f(n)。 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | $1\le T\le 10^4,1\le n\le 10^5$ | ||
| ===题解=== | ===题解=== | ||
| + | |||
| + | 设数列为m项。枚举$a_1，m$。对于这样的$a_1,m$的数列，计算其对f(a_1m+k)的贡献。发现，对$3\le k\le m$，其贡献为$\lfloor \frac {k-1}2 \rfloor$，对$m\le k\le 2m-3$，其贡献为$\lfloor \frac {2m-k-1}2 \rfloor$。设g(x)=f(x)-f(x-2)。先求g(x)，再得到f(x) | ||
| ====F - ==== | ====F - ==== | ||
2020-2021/teams/hotpot/2020nowcoder8.1596787459.txt.gz · 最后更改: 2020/08/07 16:04 由 lotk
