LOJ #6509. 「雅礼集训 2018 Day7」C

题意

给定一棵 $n$ 个点的树，树上每个点初始有一个 $0$ 或 $1$ 的数字。

考虑这样一个过程：

1. 等概率随机选择一个点作为起点
2. 等概率随机选择一个新点并沿着树上的路径移动过去，最后反转这个新点上的数字（注意只反转这个新点上的数字而非经过的所有点的数字）
3. 如果此时整棵树上的所有数字相同，则过程结束；否则回到步骤 $2$

求出期望的移动距离，对 $10^9 + 7$ 取模。

$n\le 10^5$

Luogu P4705 玩游戏

题意

有长度为 $n$ 的序列 $a$ 和长度为 $m$ 的序列 $b$

对于 $k=1,2,\dotsc,t$ 求随机两个元素 $a_i$ 和 $b_j$，$(a_i+b_j)^k$ 的期望

模 $998244353$

$n,m,t\le 10^5$

Codeforces 1034E

题意

给你两个 $2^n$ 的数组 $a_0,..,a_{2^n-1}$ 和 $b_0,..,b_{2^n-1}$

在模 $4$ 意义下求子集卷积

$n\le 21$

zx2003说多 log 过不去，不然就去写了

Codeforces 1034D

题意

你有 $n$ 个区间 $[a_i, b_i]$，定义区间的区间 $[l,r]$ 的价值是第 $l$ 个区间到第 $r$ 个区间的并的总长度

你需要找出 $k$ 个不同的区间的区间，使得它们的总价值最大

输出总价值

$1\le n \le 3 * 10^5,1 \le k \le \min{\frac{n(n+1)}{2},10^9}$

为什么模数是偶数我都敢先取模后除以2了。不知道是不是傻了。

51nod 1965

题意

求

$$\prod_{i=1}^n \sigma_0(i)^{\mu(i)+i} \mod(10^{12}+39)$$

其中 $\sigma_0(i)$ 表示 $i$ 的正约数个数，$10^{12}+39$ 是质数

$n\le 10^{11}$

51nod 1847

题意

给出 $n,k$ 求

$$\sum_{i=1}^n\sum_{j=1}^n sgcd(i,j)^k$$

其中 $sgcd(i,j)$ 表示 $i,j$ 的次大公约数，特殊地，$sgcd(1,1)=0$

对 $2^{32}$ 取模

$n\le 10^9, k\le 50$

SPOJ APS2

题意

令 $f(i)$ 表示 $i$ 的最小质因子

求 $$\sum_{i=2}^n f(i)$$

$n\le 1.234567891011*10^{12}$

题意

令 $\sigma_0(n)$ 表示 $n$ 的约数个数

求 $$\sum_{i=1}^n \sigma_0(i^3)$$

$n\le 10^{11}$

题意

令 $\sigma_0(n)$ 表示 $n$ 的约数个数

求 $$\sum_{i=1}^n \sigma_0(i^2)$$

$n\le 10^{12}$

H. Playing games

题意

你有 $n$ 堆石子，数量分别是 $a_1,..,a_n$

问最多能选出几堆使得玩 Nim游戏 满足后手必胜

$n,a_i\le 5*10^5$