Codeforces 1097G. Vladislav and a Great Legend

当时不会做

题意

给定一棵 $n$ 个点的树

对于每个非空的点集 $X\subseteq {1,2,\dotsc,n}$，定义 $f(X)$ 表示最少的能让点集 $X$ 联通的边的数量

求

$$
\sum_{X\subseteq {1,2,\dotsc,n},X\ne \varnothing} (f(X))^k
$$

模 $10^9+7$

$n\le 10^5,k\le 200$

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$