「LOJ 6509」「雅礼集训 2018 Day7」C
题意
给定一棵 \(n\) 个点的树，树上每个点初始有一个 \(0\) 或 \(1\) 的数字。
考虑这样一个过程：
- 等概率随机选择一个点作为起点
- 等概率随机选择一个新点并沿着树上的路径移动过去，最后反转这个新点上的数字（注意只反转这个新点上的数字而非经过的所有点的数字）
- 如果此时整棵树上的所有数字相同，则过程结束；否则回到步骤 \(2\)
求出期望的移动距离，对 \(10^9 + 7\) 取模。
\(n\le 10^5\)
给定一棵 \(n\) 个点的树，树上每个点初始有一个 \(0\) 或 \(1\) 的数字。
考虑这样一个过程：
求出期望的移动距离，对 \(10^9 + 7\) 取模。
\(n\le 10^5\)
有长度为 \(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\)
给你两个 \(2^n\) 的数组 \(a_0,..,a_{2^n-1}\) 和 \(b_0,..,b_{2^n-1}\)
在模 \(4\) 意义下求子集卷积
\(n\le 21\)
zx2003说多 log 过不去，不然就去写了
你有 \(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了。不知道是不是傻了。
求
\[\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}\)
给出 \(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\)
令 \(\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}\)