补题进度：6/12
怎么还这么菜啊
铁牌++
A
- 观察可知，奇数位上的一样，偶数位一样
B
题解
积性函数，学不会(真菜
update：
- 事实上根本不难
- 问题$\sum_{d|n}\phi(d)\times {\frac{n}{d}}$，其中$\phi(n)=n\prod _{p|n}(1-\frac{1}{p})$ ($p$是质数)
- 故问题可以写成求 $n\times\sum_{d|n} \prod _{p|d}(1-\frac{1}{p})$
- 由于$n$给出的方式就是通过$n=\prod_{i=1}^{m}{p_i}^{q_i}$ ($p$是质数)
- 分析一下上面的公式不难发现$p$就是每个$p_i$的取值，$d$就是$m$个$p_i$选择的情况，每个$p_i$有$q_i+1$种选择，由于每个$p_i$只要选择大于等于$1$次效果都是一样的，所以可以直接压缩这些
- 故直接枚举每个$p_i$选或不选，选的话有$q_i$的情况
- 直接状态压缩计算的时间复杂度是$O(m·2^m)$，因为有一个检查每一位是选还是不选的过程，但dfs直接考虑每一位的情况就可以省掉这个过程
- 时间复杂度$O(2^m)$
C
题解
- 分析Ha必胜的情况
- balabala
D
题解
找规律- dp[i]: 表示第i个点被选的概率
- 则$dp[i]=(dp[1]+…+dp[i-1])/(i-1)+1/n$
- 按照期望公式对每个点算贡献即可
E
题意
题解
F
题意
题解
G
题意
题解
H
题意
题解
I
题意
题解
J
题解
- 直接线段树暴力修改每个数wa到自闭，不满足取 $ mod $ 的条件.
- 即$gcd(a,b)$ % $mod$ != $gcd( a % mod$, $b$ % $mod)$ % $mod$
- 正确思路：对每个节点记录乘2和3的次数
K
题解
这道题用不到任何算法~- 考虑$\sum_{i=1}^{i=n}{\left \lfloor \frac{t-b_i}{a_i} \right \rfloor}$，可以分成$\sum_{i=1}^{i=n}{\left \lfloor \frac{t}{a_i} \right \rfloor}$ - $\sum_{i=1}^{i=n}{\left \lfloor \frac{b_i}{a_i} \right \rfloor}$，和两个的余数也要相减。
- 考虑到$a_i$只有1000，余数也小于1000，对每个$a_i$分类，二分答案，暴力判断，这里会用到前缀和加速统计余数的数量