2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day2
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day2 [2021/03/31 21:29] jxm2001 创建 |
2020-2021:teams:legal_string:jxm2001:contest:ccpc_wannafly_winter_camp_day2 [2021/05/01 20:55] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== CCPC Wannafly Camp Day1 ====== | + | ====== CCPC Wannafly Camp Day2 ====== |
| [[https://ac.nowcoder.com/acm/contest/4010|比赛链接]] | [[https://ac.nowcoder.com/acm/contest/4010|比赛链接]] | ||
| 行 41: | 行 41: | ||
| 于是 $x_j$ 的前 $y-1$ 位无限制。固定其他所有 $x$，对 $x_j\in [0,2^y-1]$，恰有一个 $x_j$ 使得 $x_1\oplus x_2\oplus \cdots x_n =k$。 | 于是 $x_j$ 的前 $y-1$ 位无限制。固定其他所有 $x$，对 $x_j\in [0,2^y-1]$，恰有一个 $x_j$ 使得 $x_1\oplus x_2\oplus \cdots x_n =k$。 | ||
| - | 于是此时 $i$ 对答案的贡献为 $\frac {\text{dp}(n,i)}{2^y}$。 | + | 于是此时 $i$ 对答案的贡献为 $\frac {\text{dp}(n,i)}{2^y}$。总时间复杂度 $O(n^2\log m)$。 |
| + | |||
| + | ps. $\text{dp}(i,j)$ 实际上可以换成 $\text{f}(i)=\sum_{j=0,2\mid j}\text{dp}(i,j),\text{g}(i)=\sum_{j=1,2\not\mid j}\text{dp}(i,j)$ 维护，时间复杂度降为 $O(n\log m)$。 | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| 行 92: | 行 94: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| - | |||
| - | |||
| - | |||
2020-2021/teams/legal_string/jxm2001/contest/ccpc_wannafly_winter_camp_day2.1617197391.txt.gz · 最后更改: 2021/03/31 21:29 由 jxm2001
