danihao123's Blog

有个很好康的结论：

\[\gcd(x^a - 1, x^b - 1) = x^{\gcd(a, b)} - 1\]

然后尝试去用常见套路（枚举gcd）化简柿子，得到：

\[\sum_{k = 1}^n (x^k - 1)\sum_{1\leq a,b\leq n} [\gcd(a, b) = k]\]

推到这里了，看到那个\(\sum_{1\leq a,b\leq n} [\gcd(a, b) = k]\)可能很多同学准备直接上莫比乌斯函数了……其实并不需要，其实那个柿子就是：

\[2\sum_{i = 1}^{\lfloor \tfrac{n}{k}\rfloor} \varphi (i) - 1\]

这个意义还是很显然的……更好的一点是这个柿子可以预处理出来，然后整除分块直接搞一波即可。

代码：

#include <cstdio>
typedef long long ll;
const ll ha = 1000000007LL;
const int maxn = 1000005;
const int N = 1000000;
ll phi[maxn], phi_S[maxn];
void sieve() {
  static bool vis[maxn];
  static int prm[maxn]; int cnt = 0;
  phi[1] = 1LL;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      prm[cnt ++] = i;
      phi[i] = i - 1;
    }
    int v;
    for(int j = 0; j < cnt && (v = i * prm[j]) <= N; j ++) {
      vis[v] = true;
      if(i % prm[j] == 0) {
        phi[v] = (phi[i] * (ll(prm[j]))) % ha;
        break;
      } else {
        phi[v] = (phi[i] * phi[prm[j]]) % ha;
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    phi_S[i] = (phi_S[i - 1] + phi[i]) % ha;
  }
  for(int i = 1; i <= N; i ++) {
    phi_S[i] = ((2LL * phi_S[i]) % ha - 1LL + ha) % ha;
  }
}

ll pow_mod(ll a, ll b) {
  ll ans = 1LL, res = a;
  while(b) {
    if(1LL & b) ans = (ans * res) % ha;
    res = (res * res) % ha;
    b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

ll pre_sum(ll x, ll r) {
  ll p = pow_mod(x, r);
  p = (p - 1LL + ha) % ha;
  p = (p * inv(x - 1LL)) % ha;
  return p;
}
ll seg_sum(ll x, int a, int b) {
  if(x == 1LL) return 0;
  ll len = b - a + 1;
  ll ret = (pre_sum(x, b + 1) - pre_sum(x, a) + ha) % ha;
  ret = (ret - len + ha) % ha;
  return ret;
}
ll calc(ll x, int n) {
  ll ans = 0;
  for(int i = 1; i <= n;) {
    int v = n / i;
    int nx = n / v;
    ll delta = (seg_sum(x, i, nx) * phi_S[v]) % ha;
    ans = (ans + delta) % ha;
    i = nx + 1;
  }
  return ans;
}

int main() {
  sieve();
  int T; scanf("%d", &T);
  while(T --) {
    int x, n; scanf("%d%d", &x, &n);
    printf("%lld\n", calc(x, n));
  }
  return 0;
}

第一次用到第二类斯特林数……

首先众所周知第二类斯特林数有一个很好康的式子：

\[x^k = \sum_{i = 0}^k S(k, i) x^{\underline{i}}\]

然后带进去试试？一番化简之后得到：

\[E_u = \sum_{i = 0}^k S(k, i) \sum_{v = 1}^n dist(u, v)^{\underline{i}}\]

那个下降幂很恶心……把它强行搞成组合数后发现：

\[E_u = \sum_{i = 0}^k S(k, i) i! \sum_{v = 1}^n \binom{dist(u, v)}{i}\]

然后考虑每个点预处理后面那个和式……显然可以树形DP苟。用经典的树形DP套路，设两个状态分别表示一个点的子树内部的贡献以及外面的点给他的贡献。至于转移，由于那是个组合数，所以可以考虑用Pascal定理苟……

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <utility>
const int maxn = 50005;
const int maxk = 505;
const int ha = 10007;
int first[maxn];
int next[maxn << 1], to[maxn << 1];
int cnt;
void add_edge(int u, int v) {
  cnt ++;
  next[cnt] = first[u]; first[u] = cnt;
  to[cnt] = v;
}

int n, k;
int down[maxn][maxk];
void dfs_1(int x, int fa = 0) {
  down[x][0] = 1;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != fa) {
      dfs_1(v, x);
      down[x][0] = (down[x][0] + down[v][0]) % ha;
      for(int j = 1; j <= k; j ++) {
        down[x][j] = (down[x][j] + down[v][j] + down[v][j - 1]) % ha;
      }
    }
  }
}
int up[maxn][maxk];
void dfs_2(int x, int fa = 0) {
  if(fa) {
    up[x][0] = n - down[x][0];
    for(int j = 1; j <= k; j ++) {
      up[x][j] = (up[fa][j] + up[fa][j - 1] + down[fa][j] + down[fa][j - 1]) % ha;
      up[x][j] = (up[x][j] - (2 * down[x][j - 1]) % ha + ha) % ha;
      up[x][j] = (up[x][j] - down[x][j] + ha) % ha;
      if(j > 1) up[x][j] = (up[x][j] - down[x][j - 2] + ha) % ha;
    }
  }
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != fa) {
      dfs_2(v, x);
    }
  }
}

int S[maxk][maxk];
int fac[maxn];
void process() {
  S[1][1] = 1;
  for(int i = 2; i <= k; i ++) {
    S[i][0] = 0;
    for(int j = 1; j < i; j ++) {
      S[i][j] = ((j * S[i - 1][j]) % ha + S[i - 1][j - 1]) % ha;
    }
    S[i][i] = 1;
  }
  fac[0] = 1;
  for(int i = 1; i <= n; i ++) {
    fac[i] = (fac[i - 1] * (i % ha)) % ha;
  }
}

int main() {
  int T; scanf("%d", &T);
  n = 50000; k = 500; process();
  while(T --) {
    scanf("%d%d", &n, &k);
    cnt = 0; memset(first, 0, sizeof(first));
    for(int i = 0; i < n - 1; i ++) {
      int u, v; scanf("%d%d", &u, &v);
      add_edge(u, v); add_edge(v, u);
    }
    memset(down, 0, sizeof(down));
    memset(up, 0, sizeof(up));
    dfs_1(1); dfs_2(1);
    for(int i = 1; i <= n; i ++) {
      int ans = 0;
      for(int j = 1; j <= k; j ++) {
        int f_v = (down[i][j] + up[i][j]) % ha;
        ans = (ans + (S[k][j] * ((f_v * fac[j]) % ha)) % ha) % ha;
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}