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\)