danihao123's Blog

给你一张\(n\)个点\(m\)条边的有向图，设从\(1\)到\(n\)的最短路为\(d\)，那么请问有多少\(1\)到\(n\)的路径（可以是非简单路径）满足其长度在\([d, d + K]\)中，如果答案为无限大的话输出\(-1\)。

\(1\leq n\leq 10^5, 1\leq m\leq 2\times 10^5, 0\leq K\leq 50\)。

一张\(n\)个点的图，初始没边，然后要求你支持以下操作：

• 给定\((x, y)\)，在\(x\)和\(y\)两点间添加一条长度为\(i\)的边（假设这是第\(i\)次操作）。
• 给定\(k\)，删除当前图中边权最大的\(k\)条边。
• 撤销上一次操作。保证存在上一次操作且不是撤销操作。

共\(m\)次操作，每次操作后输出当前图最小生成树的边权和（不存在的话输出\(0\)）。

\(1\leq n\leq 300000, 1\leq m\leq 500000\)。

给你一个集合\(S\)（保证其中元素都为小于\(n\)的自然数），定义一棵合法的树为一棵编号满足堆的性质，且非叶子节点都一定有两个可能非叶子的儿子，同时有\(c(c\in S)\)个一定为叶子的儿子。对于所有\(i = 1\ldots n\)，求有多少大小为\(i\)的形态不同的合法的树。

\(n\leq 200000\)。

定义分拆数\(f(x)\)表示将\(x\)拆为若干正整数的本质不同方案数。对于\(i = 1\ldots n\)，输出\(f(i)\)。

\(1\leq n\leq 10^5\)。

给你一个大小为\(n\)的集合\({c_1, c_2,\ldots ,c_n}\)，规定合法的二叉树为带点权且点权都属于给定集合中的点的数。对于任意整数$i\in [1, m]$，求出有多少不同的点权和为\(i\)的二叉树并输出之。

\(1\leq n, m, c_i\leq 10^5\)。

好前一段时间因为一些神必原因……博客放到了https://yahyachan.github.io。然后因为我回学校了所以接下来很长时间可能会继续用这个博客？

我谔谔，还是说这题……

对于询问\([l, r]\)，考虑所有数在其中第一次出现的位置，如果说这个数在整个区间里只出现了一次，那么这个数下一次出现的位置一定大于\(r\)。

因此我们用扫描线搞一下就好啦……

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
using pii = std::pair<int, int>;
const int maxn = 500005;
const int maxno = maxn << 2;
pii maxv[maxno];
void maintain(int o) {
  maxv[o] = std::max(maxv[o << 1], maxv[o << 1 | 1]);
}
void build_tree(int o, int L, int R) {
  if(L == R) {
    maxv[o] = std::make_pair(-1, -1);
  } else {
    int M = (L + R) / 2;
    build_tree(o << 1, L, M);
    build_tree(o << 1 | 1, M + 1, R);
    maintain(o);
  }
}
void modify(int o, int L, int R, const int &p, const pii &v) {
  if(L == R) {
    maxv[o] = v;
  } else {
    int M = (L + R) / 2;
    if(p <= M) {
      modify(o << 1, L, M, p, v);
    } else {
      modify(o << 1 | 1, M + 1, R, p, v);
    }
    maintain(o);
  }
}
pii query(int o, int L, int R, const int &ql, const int &qr) {
  if(ql <= L && R <= qr) {
    return maxv[o];
  } else {
    int M = (L + R) / 2;
    pii ret = std::make_pair(-100, -100);
    if(ql <= M) ret = std::max(ret, query(o << 1, L, M, ql, qr));
    if(qr > M) ret = std::max(ret, query(o << 1 | 1, M + 1, R, ql, qr));
    return ret;
  }
}

int rec[maxn], next[maxn];
int A[maxn];
std::vector<pii> que[maxn]; int ans[maxn];
int main() {
  int n; scanf("%d", &n);
  std::fill(rec, rec + maxn, n + 1);
  for(int i = 1; i <= n; i ++) scanf("%d", &A[i]);
  for(int i = n; i >= 1; i --) {
    next[i] = rec[A[i]];
    rec[A[i]] = i;
  }
  int q; scanf("%d", &q);
  for(int i = 1; i <= q; i ++) {
    int l, r; scanf("%d%d", &l, &r);
    que[l].push_back({r, i});
  }
  build_tree(1, 1, n);
  for(int i = 1; i <= 500000; i ++) {
    if(rec[i] <= n) {
      modify(1, 1, n, rec[i], {next[rec[i]], i});
    }
  }
  for(int i = 1; i <= n; i ++) {
    for(const pii &g : que[i]) {
      int r = g.first, id = g.second;
      pii tmp = query(1, 1, n, i, r);
      if(tmp.first <= r) {
        ans[id] = 0;
      } else {
        ans[id] = tmp.second;
      }
    }
    int nx = next[i];
    if(nx <= n) {
      modify(1, 1, n, nx, {next[nx], A[i]});
    }
  }
  for(int i = 1; i <= q; i ++) {
    printf("%d\n", ans[i]);
  }
  return 0;
}

沿用约数个数和一题的思路……可以列出此式：

\[\sigma_1(ij) = \sum_{a | i}\sum_{b | j} ab[\gcd(\frac{i}{a}, b) = 1]\]

然后我们考虑去化简原式：

\[
\begin{aligned}
\sum_{i = 1}^n\sum_{j = 1}^n\sum_{a | i}\sum_{b | j} ab\sum_{d | \frac{i}{a}, d | j}\mu(d)
\end{aligned}
\]

接下来我们考虑枚举\(d\)，但是\(a\)和\(b\)的贡献又有点麻烦了……

\(b\)的贡献还好说，直接枚举\(b\)本身是\(d\)的多少倍就是\(\sum_{b = 1}^{\lfloor\frac{n}{d}\rfloor} bd\lfloor\frac{n}{bd}\rfloor\)。那\(a\)的贡献如何考虑？

我们考虑直接去枚举\(a\)本身……可以注意到一定有\(a\le\lfloor\frac{n}{d}\rfloor\)（因为\(\frac{i}{a}\ge d\)），所以直接枚举\(a\)本身之后再考虑\(\lfloor\frac{n}{a}\rfloor\)范围内\(d\)的倍数的数量即可（相当于找\(\frac{i}{a}\)），因此贡献为\(\sum_{a = 1}^{\lfloor\frac{n}{d}\rfloor} a\lfloor\frac{n}{ad}\rfloor\)。

那么继续化简原式：

\[
\begin{aligned}
\quad&\sum_{d = 1}^n\mu(d)\sum_{b = 1}^{\lfloor\frac{n}{d}\rfloor} bd\lfloor\frac{n}{bd}\rfloor\sum_{a = 1}^{\lfloor\frac{n}{d}\rfloor} a\lfloor\frac{n}{ad}\rfloor\\
=&\sum_{d = 1}^n\mu(d)d(\sum_{i = 1}^{\lfloor\frac{n}{d}\rfloor} i\lfloor\frac{n}{id}\rfloor)^2\\
=&\sum_{d = 1}^n\mu(d)d S_1^2(\lfloor\frac{n}{d}\rfloor)
\end{aligned}
\]

此处\(S_1\)表示\(\sigma_1\)的前缀和。

接下来预处理\(\mu(d)d\)的前缀和，考虑杜教筛。我们发现该函数和\(\mathrm{id}\)卷出来就是\(\epsilon\)（证明可以考虑贝尔级数……这种方式非常有效，并且还能帮我们找到需要卷的函数，我有时间会专门撰文写一下），所以杜教筛一波即可。这部分总复杂度为\(O(n^{\frac{2}{3}})\)。

至于\(S_1\)，我们考虑不大于\(n^{\frac{2}{3}}\)可以直接预处理，剩下的用时就用\(O(\sqrt{n})\)的方法求（考虑到反演不会用到\(S_1\)的重复状态所以不需要记忆化）。用类似于杜教筛复杂度证明的方法可以证明该部分总复杂度为\(O(n^{\frac{2}{3}})\)。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <unordered_map>
const int N = 1000000;
using ll = long long;
const ll ha = 1000000007LL;
const ll i2 = 500000004LL;
ll mud[N + 5], sig_1[N + 5];
int prm[N + 5]; bool vis[N + 5];
void sieve() {
  int cnt = 0;
  mud[1] = 1;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      mud[i] = (ha - i);
      prm[cnt ++] = i;
    }
    for(int j = 0; j < cnt; j ++) {
      int v = i * prm[j];
      if(v > N) break;
      vis[v] = true;
      if(i % prm[j] == 0) {
        mud[v] = 0; break;
      } else {
        mud[v] = (mud[i] * mud[prm[j]]) % ha;
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    for(int j = i; j <= N; j += i) {
      sig_1[j] = (sig_1[j] + (ll(i))) % ha;
    }
  }
  for(int i = 1; i <= N; i ++) {
    mud[i] = (mud[i - 1] + mud[i]) % ha;
    sig_1[i] = (sig_1[i - 1] + sig_1[i]) % ha;
  }
}

std::unordered_map<ll, ll> ma;
ll calc_id(ll x) {
  ll v1 = x, v2 = x + 1LL;
  if(x & 1LL) {
    v2 /= 2LL;
  } else {
    v1 /= 2LL;
  }
  return ((v1 * v2) % ha);
}
ll calc_mud(ll n) {
  if(n <= (ll(N))) return mud[n];
  if(ma.count(n)) return ma[n];
  ll ans = 1, las = 1;
  for(ll i = 2; i <= n;) {
    ll next = n / (n / i);
    ll nv = calc_id(next);
    ll ns = (nv - las + ha) % ha;
    ans = (ans - (ns * calc_mud(n / i)) % ha + ha) % ha;
    las = nv; i = next + 1LL;
  }
  ma[n] = ans; return ans;
}
ll calc_s1(ll n) {
  if(n <= (ll(N))) return sig_1[n];
  ll ans = 0, las = 0;
  for(ll i = 1; i <= n;) {
    ll next = n / (n / i);
    ll nv = calc_id(next);
    ll ns = (nv - las + ha) % ha;
    ans = (ans + (ns * (n / i)) % ha) % ha;
    las = nv; i = next + 1LL;
  }
  return ans;
}
ll calc(ll n) {
  ll ans = 0, las = 0;
  for(ll i = 1; i <= n;) {
    ll next = n / (n / i);
    ll nv = calc_mud(next); ll ns = (nv - las + ha) % ha;
    ll pv = calc_s1(n / i); pv = (pv * pv) % ha;
    ans = (ans + (ns * pv) % ha) % ha;
    las = nv; i = next + 1LL;
  }
  return ans;
}

int main() {
  sieve();
  ll n; scanf("%lld", &n);
  printf("%lld\n", calc(n));
  return 0;
}

首先我们有这样一个式子：

\[d(ij) = \sum_{a | i}\sum_{b | j} [\gcd(\frac{i}{a}, b) = 1]\]

怎样理解这一结论呢？我们知道\(ij\)的约数\(d\)一定可以被分解为\(ab\)使得\(a | i, b | j\)，但这种划分可能会非常的多，我们要保证每个约数\(d\)只有一种划分被统计过。

那么考虑上述划分方法。对于\(i\)和\(j\)中一个有一个没有的质因子，是一定会划分到\(a\)和\(b\)中固定的一个的。那么考虑一个在\(i\)和\(j\)中都出现的质因子\(p\)，假设\(p\)在\(d\)中出现的次数超过了\(i\)和\(j\)中任何一个的话，那么\(p\)在\(a\)中一定会尽可能多的出现（否则\(\frac{i}{a}\)中会出现\(p\)，而这样无论如何一定有\(p | b\)，因此会不满足\(\gcd(\frac{i}{a}, b) = 1\)）。如果没超过呢？那么一定会全部划分到\(a\)中（其他情况下有\(p | b\)并且会出现\(p | \frac{i}{a}\)）。

下面考虑应用这个结论（为了方便，使用等价的\(d(ij) = \sum_{a | i}\sum_{b | j} [\gcd(a, b) = 1]\)，假设\(n\le m\)）：

\[
\begin{aligned}
\quad&\sum_{i = 1}^n\sum_{j = 1}^m \sum_{a | i}\sum_{b | j}\sum_{d | i, d | j}\mu(d)\\
=&\sum_{d = 1}^n\mu(d)\sum_{a = 1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{ad}\rfloor\sum_{b = 1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{bd}\rfloor\\
=&\sum_{d = 1}^n\mu(d)\sum_{a = 1}^{\lfloor\frac{n}{d}\rfloor}d(a)\sum_{b = 1}^{\lfloor\frac{m}{d}\rfloor}d(b)
\end{aligned}
\]

后面两个和式可以随便\(O(n)\)欲处理一下（然后我当初写了个\(O(n\sqrt{n})\)的神必预处理……），然后这个题做完力，，，

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <queue>
#include <utility>
typedef long long int_t;
const int maxn = 50005;
int_t miu[maxn], miu_s[maxn], f[maxn];
void process() {
  static bool vis[maxn];
  static int prm[maxn]; int cnt = 0;
  const int N = 50000;
  miu[1] = 1LL;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      miu[i] = -1LL; prm[cnt ++] = i;
    }
    for(int j = 0; j < cnt && prm[j] * i <= N; j ++) {
      int v = prm[j] * i;
      vis[v] = true;
      if(i % prm[j] == 0) {
        miu[v] = 0; break;
      } else {
        miu[v] = miu[i] * -1;
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    miu_s[i] = miu_s[i - 1] + miu[i];
  }
  for(int i = 1; i <= N; i ++) {
    for(int j = 1; j <= i;) {
      int nx = i / (i / j);
      f[i] += (int_t(nx - j + 1)) * (int_t(i / j));
      j = nx + 1;
    }
  }
}

int_t solve(int n, int m) {
  int_t ans = 0;
  for(int i = 1; i <= std::min(n, m);) {
    int nx = std::min(m / (m / i), n / (n / i));
    ans += (miu_s[nx] - miu_s[i - 1]) * f[m / i] * f[n / i];
    i = nx + 1;
  }
  return ans;
}
#ifdef LOCAL
#define LO "%I64d"
#else
#define LO "%lld"
#endif
int main() {
  process(); int T;
  scanf("%d", &T);
  while(T --) {
    int n, m; scanf("%d%d", &n, &m);
    printf(LO, solve(n, m)); puts("");
  }
  return 0;
}

颓一波式子可以发现答案就是\(ABA^T-CA^T\)。然后发现对于一个\(B\)中的元素\(B_{i, j}\)要对答案做出贡献要求\(A_i\)和\(A_j\)都为1，而\(A_i\)为1会导致答案减去一个\(C_i\)。

因此我们可以分别对\(B\)中元素和\(A\)中元素建点。\(B\)中元素会带来收益，但是要求依赖两个\(A\)中元素。而\(A\)中元素会带来一定的笋丝。这个就已经事很明显的最大权闭合子图力，，，

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
const int maxn = 505;
const int maxno = 500 * 500 + 500 + 5;
const int maxm = 2 * (500 * 500 * 3 + 500 + 5);
int first[maxno];
int next[maxm], to[maxm], flow[maxm], cap[maxm];
int gcnt = 0;
void add_edge(int u, int v, int c) {
  gcnt ++;
  next[gcnt] = first[u]; first[u] = gcnt;
  to[gcnt] = v; cap[gcnt] = c; flow[gcnt] = 0;
}
void ins_edge(int u, int v, int c) {
  add_edge(u, v, c); add_edge(v, u, 0);
}
int rev(int i) {
  if(1 & i) {
    return i + 1;
  } else {
    return i - 1;
  }
}

int d[maxno];
int s, t, num;
bool bfs() {
  static bool vis[maxno];
  std::fill(vis, vis + num + 1, false);
  std::fill(d, d + num + 1, 0);
  std::queue<int> Q; Q.push(s);
  d[s] = 1; vis[s] = true;
  while(!Q.empty()) {
    int u = Q.front(); Q.pop();
    for(int i = first[u]; i; i = next[i]) {
      int v = to[i];
      if(!vis[v] && cap[i] > flow[i]) {
        d[v] = d[u] + 1;
        Q.push(v); vis[v] = true;
      }
    }
  }
  return vis[t];
}
int cur[maxno];
int dfs(int x, int a) {
  if(a == 0 || x == t) return a;
  int ret = 0;
  for(int &i = cur[x]; i; i = next[i]) {
    int v = to[i], f;
    if(d[v] == d[x] + 1 && (f = dfs(v, std::min(a, cap[i] - flow[i]))) > 0) {
      ret += f; a -= f;
      flow[i] += f; flow[rev(i)] -= f;
      if(a == 0) break;
    }
  }
  if(a > 0) d[x] = -1;
  return ret;
}
int dinic() {
  int ret = 0;
  while(bfs()) {
    for(int i = 0; i <= num; i ++) cur[i] = first[i];
    ret += dfs(s, 0x7f7f7f7f);
  }
  return ret;
}

int n;
int main() {
  int ans = 0;
  scanf("%d", &n);
  s = 0, t = n * n + n + 1;
  num = t;
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n; j ++) {
      int u = (i - 1) * n + j; int val; scanf("%d", &val);
      ans += val; ins_edge(s, u, val);
      ins_edge(u, n * n + i, 0x7f7f7f7f);
      ins_edge(u, n * n + j, 0x7f7f7f7f);
    }
  }
  for(int i = 1; i <= n; i ++) {
    int val; scanf("%d", &val);
    ins_edge(n * n + i, t, val);
  }
  ans -= dinic();
  printf("%d\n", ans);
  return 0;
}

首先这个题和能量采集几乎完全一致……稍微有点反演常识的人都知道答案事\(\sum_{i = 1}^n\varphi(i)\lfloor\frac{n}{i}\rfloor^2\)，然后你需要用\(\varphi\)的前缀和，这个东西直接杜教筛搞一波就行了。这样总复杂度事\(O(n^{\frac{2}{3}})\)的，下面给出证明。

先考虑杜教筛的部分。杜教筛可以看做一个转移复杂度为\(O(\sqrt{n})\)的DP，他的状态一定是通过总的\(n\)整除一个数得到的。不大于\(n^{\frac{2}{3}}\)的状态我们都事先预处理，那么我们假设所有大于\(n^{\frac{2}{3}}\)的状态都被计算了一遍，这些状态一定事通过\(n\)整除一个不大于\(n^{\frac{1}{3}}\)的数得到的。因此复杂度为：

\[\sum_{i = 1}^{n^{\frac{1}{3}}} \sqrt{\lfloor\frac{n}{i}\rfloor}\leq \int_0^{n^{\frac{1}{3}}} \sqrt{\frac{n}{x}}\mathrm{d}x = 2n^{\frac{2}{3}} = O(n^{\frac{2}{3}})\]

至于莫比乌斯反演，不考虑杜教筛的复杂度的话就只是\(O(\sqrt{n})\)而已了。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <utility>
using ll = long long;
constexpr ll ha = 1000000007LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1, 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);
}

const int N = 10000000;
ll phi[N + 1]; int prm[N + 1]; bool vis[N + 1];
void sieve() {
  phi[1] = 1; vis[1] = true;
  int cnt = 0;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      phi[i] = i - 1; prm[cnt ++] = i;
    }
    for(int j = 0; j < cnt; j ++) {
      int v = i * prm[j]; if(v > N) break;
      vis[v] = true;
      if(i % prm[j] == 0) {
        phi[v] = phi[i] * prm[j]; break;
      } else {
        phi[v] = phi[i] * phi[prm[j]];
      }
    }
  }
  for(int i = 1; i <= N; i ++) {
    phi[i] = (phi[i] + phi[i - 1]) % ha;
  }
}

std::unordered_map<ll, ll> ma;
const ll i2 = inv(2LL);
ll phi_sum(ll n) {
  if(n <= (ll(N))) return phi[n];
  if(ma.count(n)) return ma[n];
  ll fg = (n % ha) * ((n + 1LL) % ha) % ha * i2 % ha;
  for(ll i = 2; i <= n;) {
    ll next = n / (n / i);
    ll len = (next - i + 1LL) % ha;
    fg = (fg - (len * phi_sum(n / i)) % ha + ha) % ha;
    i = next + 1LL;
  }
  ma[n] = fg; return fg;
}
ll calc(ll n) {
  ll ans = 0, las = 0;
  for(ll i = 1; i <= n;) {
    ll next = n / (n / i);
    ll b = ((n / i) % ha) * ((n / i) % ha) % ha;
    ll ns = phi_sum(next);
    ans = (ans + (((ns - las + ha) % ha) * b % ha)) % ha; las = ns;
    i = next + 1LL;
  }
  return ans;
}

int main() {
  sieve();
  ll n; scanf("%lld", &n);
  printf("%lld\n", calc(n));
  return 0;
}