[51Nod 1220]约数之和

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

\[\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;
}

[LibreOJ 2185][SDOI2015]约数个数和

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

\[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;
}

[LibreOJ 2100][TJOI2015]线性代数

颓一波式子可以发现答案就是\(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;
}

[51Nod 1237]最大公约数之和 V3

首先这个题和能量采集几乎完全一致……稍微有点反演常识的人都知道答案事\(\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;
}

[BZOJ 4025]二分图

只会做水题力……qwq(搞错大小写,自裁请

每条边存在的时间事一个区间,因此考虑线段树分治……首先当然要写一个可撤销并查集。

然后每个点维护他到父亲的边的边权膜2,合并啥的和食物链就很类似力……然后判定已联通两点间边数的奇偶性就直接把两个点到根的值加起来就行了,因为LCA到根的部分会算两遍,对答案无影响。

代码:

/**************************************************************
    Problem: 4025
    User: danihao123
    Language: C++
    Result: Accepted
    Time:9928 ms
    Memory:34840 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
const int maxn = 100005;
const int maxno = maxn << 2;
const int maxm = 200005;
int n, m, T;
 
int p[maxn], siz[maxn], d[maxn];
void init_dsu() {
  for(int i = 1; i <= n; i ++) {
    p[i] = i; siz[i] = 1; d[i] = 0;
  }
}
int get_fa(int x) {
  if(p[x] == x) {
    return x;
  } else {
    return get_fa(p[x]);
  }
}
int get_d(int x) {
  if(p[x] == x) {
    return 0;
  } else {
    return (d[x] + get_d(p[x])) % 2;
  }
}
typedef std::pair<int, int> upd;
upd link_set(int x, int y, int v) {
  if(siz[x] > siz[y]) std::swap(x, y);
  p[x] = y; siz[y] += siz[x]; d[x] = v;
  return std::make_pair(x, y);
}
upd merge_set(int x, int y) {
  int v = (get_d(x) + get_d(y) + 1) % 2;
  return link_set(get_fa(x), get_fa(y), v);
}
void unlink_set(const upd &pr) {
  int x = pr.first, y = pr.second;
  p[x] = x; siz[y] -= siz[x]; d[x] = 0;
}
bool is_same(int x, int y) {
  return (get_fa(x) == get_fa(y));
}
 
std::vector<upd> event[maxno];
std::stack<std::pair<int, upd> > S;
void update(int o, int L, int R, int ql, int qr, upd v) {
  if(ql <= L && R <= qr) {
    event[o].push_back(v);
  } else {
    int M = (L + R) / 2;
    if(ql <= M) update(o << 1, L, M, ql, qr, v);
    if(qr > M) update(o << 1 | 1, M + 1, R, ql, qr, v);
  }
}
int val[maxno];
void solve(int o, int L, int R) {
  for(int i = 0; i < event[o].size(); i ++) {
    const upd &pr = event[o][i];
    int x = pr.first, y = pr.second;
    if(is_same(x, y)) {
      if((get_d(x) + get_d(y)) % 2 == 0) {
        val[o] = 0;
        break;
      }
    } else {
      S.push(std::make_pair(o, merge_set(x, y)));
    }
  }
  if(L == R) {
    if(val[o] != 0) val[o] = 1;
  } else {
    if(val[o] != 0) {
      int M = (L + R) / 2;
      solve(o << 1, L, M);
      solve(o << 1 | 1, M + 1, R);
    }
  }
  while((!S.empty()) && S.top().first >= o) {
    upd v = S.top().second; S.pop();
    unlink_set(v);
  }
}
void print(int o, int L, int R) {
  if(L == R) {
    if(val[o]) {
      puts("Yes");
    } else {
      puts("No");
    }
  } else {
    if(val[o] != -1) {
      val[o << 1] = val[o];
      val[o << 1 | 1] = val[o];
    }
    int M = (L + R) / 2;
    print(o << 1, L, M);
    print(o << 1 | 1, M + 1, R);
  }
}
 
int main() {
  memset(val, -1, sizeof(val));
  scanf("%d%d%d", &n, &m, &T);
  for(int i = 1; i <= m; i ++) {
    int u, v, s, t; scanf("%d%d%d%d", &u, &v, &s, &t);
    s ++; if(s <= t) update(1, 1, T, s, t, std::make_pair(u, v));
  }
  init_dsu(); solve(1, 1, T); print(1, 1, T);
  return 0;
}

[LibreOJ 2472][九省联考2018]IIIDX

一直没有填的坑……今天乱写了写跑过了然后厚颜无耻凑一篇题解

还有样例过于草(出题人钦点淫梦运营

考虑从小到大枚举序列的每一位置\(p\),然后我们发现每一位置的值的合法性事单调的(小的合法,大了就不合法),这样可以对每一个位置二分答案。

然后我们考虑二分完了答案\(x\)怎么判定。把值离散化一下然后用一个线段树来维护\(T_i\)(表示当前还没有被预定的大于等于\(i\)的数有多少个),然后判定答案就看到\(x\)的前缀区间是否都不小于\(p\)所在子树的大小。同时注意顺次枚举每个点的时候要去除他对他父亲的影响,然后每次一个点确定是什么值了也要修改对应的前缀区间。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
using R = long double;
const int maxn = 500005;
const int maxno = maxn << 2;
int n; R k;
int minv[maxno], addv[maxno];
void maintain(int o) {
  int lc = o << 1, rc = o << 1 | 1;
  minv[o] = std::min(minv[lc], minv[rc]);
}
void paint(int o, int v) {
  addv[o] += v; minv[o] += v;
}
void pushdown(int o) {
  if(addv[o] != 0) {
    int lc = o << 1, rc = o << 1 | 1;
    paint(lc, addv[o]); paint(rc, addv[o]);
    addv[o] = 0;
  }
}

int left[maxn];
void build_tree(int o, int L, int R) {
  // addv[o] = 0;
  if(L == R) {
    minv[o] = left[L];
  } else {
    int M = (L + R) / 2;
    build_tree(o << 1, L, M);
    build_tree(o << 1 | 1, M + 1, R);
    maintain(o);
  }
}
void update(int o, int L, int R, int ql, int qr, int v) {
  if(ql <= L && R <= qr) {
    paint(o, v);
  } else {
    pushdown(o);
    int M = (L + R) / 2;
    if(ql <= M) update(o << 1, L, M, ql, qr, v);
    if(qr > M) update(o << 1 | 1, M + 1, R, ql, qr, v);
    maintain(o);
  }
}
const int INF = 0x7f7f7f7f;
int query_min(int o, int L, int R, int ql, int qr) {
  if(ql <= L && R <= qr) {
    return minv[o];
  } else {
    pushdown(o);
    int M = (L + R) / 2, ans = INF;
    if(ql <= M) ans = std::min(ans, query_min(o << 1, L, M, ql, qr));
    if(qr > M) ans = std::min(ans, query_min(o << 1 | 1, M + 1, R, ql, qr));
    return ans;
  }
}

int d[maxn], d2[maxn];
int lsiz;
void process() {
  std::sort(d + 1, d + 1 + n);
  std::sort(d2 + 1, d2 + 1 + n);
  lsiz = std::unique(d2 + 1, d2 + 1 + n) - d2 - 1;
  for(int i = 1; i <= n; i ++) {
    d[i] = std::lower_bound(d2 + 1, d2 + 1 + lsiz, d[i]) - d2;
    left[d[i]] ++;
  }
  for(int i = lsiz - 1; i >= 1; i --) {
    left[i] += left[i + 1];
  }
  build_tree(1, 1, lsiz);
}
int A[maxn], siz[maxn];
void solve() {
  for(int i = n; i >= 1; i --) {
    siz[i] ++;
    int f = (int)floor((R(i)) / k);
    siz[f] += siz[i];
  }
  for(int i = 1; i <= n; i ++) {
    int f = (int)floor((R(i)) / k);
    if(f > 0) {
      update(1, 1, lsiz, 1, A[f], siz[i]);
    }
    int L = (f == 0) ? 1 : A[f], R = lsiz, ret;
    while(true) {
      if(R - L <= 3) {
        for(int j = R; j >= L; j --) {
          if(query_min(1, 1, lsiz, 1, j) >= siz[i]) {
            ret = j; break;
          }
        }
        break;
      }
      int M = L + (R - L) / 2;
      if(query_min(1, 1, lsiz, 1, M) >= siz[i]) {
        L = M;
      } else {
        R = M;
      }
    }
    A[i] = ret; update(1, 1, lsiz, 1, ret, -siz[i]);
  }
}

int main() {
  scanf("%d%Lf", &n, &k);
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &d[i]); d2[i] = d[i];
  }
  process(); solve();
  for(int i = 1; i <= n; i ++) {
    if(i > 1) putchar(' ');
    printf("%d", d2[A[i]]);
  }
  puts(""); return 0;
}

[BZOJ 2654]tree

APIO的时候听了一下wqs二分,做了这题,然后现在才写题解……

wqs二分的思路大抵就是你要求必须选\(k\)个,那就二分每个操作的一个“额外代价”,然后进行没有限制的选择。然后最后选出来的个数事和你二分的代价正相关/反相关的。

这道题的话,就二分选择黑边的代价,然后跑一般的最小生成树(有相同边权时要选择黑边!)。当然我们会遇到一个问题,就是二分到\(x\)的时候选的比\(k\)多,到\(x + 1\)的时候又比\(k\)少了。这道题的处理方法,事考虑代价为\(x\)时,其实存在选\(k\)个的最优解(如果说大于\(x\)那就没了),因此我们钦点代价为\(x\)跑一遍限制只能选\(k\)条黑边的最短路即可。

代码:

/**************************************************************
    Problem: 2654
    User: danihao123
    Language: C++
    Result: Accepted
    Time:5756 ms
    Memory:5856 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
const int maxn = 50005;
const int maxm = 100005;
struct Edge {
  int u, v, d;
  int typ;
  bool operator <(const Edge &res) const {
    if(d == res.d) {
      return typ < res.typ;
    } else {
      return d < res.d;
    }
  }
};
 
Edge E[maxm];
int n, m, need;
 
int par[maxn], siz[maxn];
void init_dsu() {
  for(int i = 1; i <= n; i ++) {
    par[i] = i;
    siz[i] = 1;
  }
}
int get_fa(int x) {
  if(par[x] == x) {
    return x;
  } else {
    return (par[x] = get_fa(par[x]));
  }
}
void link_set(int x, int y) {
  if(siz[x] > siz[y]) std::swap(x, y);
  siz[y] += siz[x];
  par[x] = y;
}
void merge_set(int x, int y) {
  return link_set(get_fa(x), get_fa(y));
}
bool is_same(int x, int y) {
  return (get_fa(x) == get_fa(y));
}
 
typedef long long ll;
int ans = 0x7fffffff;
bool kruskal(int delta) {
  std::vector<Edge> vec;
  for(int i = 1; i <= m; i ++) {
    Edge e = E[i];
    if(e.typ == 0) {
      e.d += delta;
    }
    vec.push_back(e);
  }
  std::sort(vec.begin(), vec.end());
  int used = 0; ll tot = -(ll(delta)) * (ll(need));
  init_dsu();
  for(int i = 0; i < m; i ++) {
    const Edge &e = vec[i];
    int u = e.u, v = e.v;
    if(!is_same(u, v)) {
      if(used == need && e.typ == 0) continue;
      merge_set(u, v); tot += e.d;
      if(e.typ == 0) used ++;
    }
  }
  if(used == need) {
    ans = std::min(ans, (int(tot)));
    return true;
  } else {
    return false;
  }
}
 
int main() {
  scanf("%d%d%d", &n, &m, &need);
  for(int i = 1; i <= m; i ++) {
    scanf("%d%d%d%d", &E[i].u, &E[i].v, &E[i].d, &E[i].typ);
    E[i].u ++; E[i].v ++;
  }
  int L = -10000001, R = 10000001;
  while(true) {
#ifdef LOCAL
    printf("Range (%d, %d)\n", L, R);
    fflush(stdout);
#endif
    if(R - L <= 3) {
      for(int i = R; i >= L; i --) {
        if(kruskal(i)) {
          break;
        }
      }
      break;
    }
    int M = L + (R - L) / 2;
    if(kruskal(M)) {
      L = M;
    } else {
      R = M;
    }
  }
  printf("%d\n", ans);
  return 0;
}

[BZOJ 1004][HNOI2008]Cards

肉肉肉肉,,,

碰置换群啥的不是第一次了……这个题就是给你一堆置换(不要忘记还有一个幺元啊),然后限制颜色数量,求本质不同解个数。那么考虑使用Burnside引理,接下来考虑怎么计算每个置换的不动点数量,这个要求每个循环的颜色一致(不就事Polya定理了吗),所以说可以用背包DP搞一搞。

代码:

/**************************************************************
    Problem: 1004
    User: danihao123
    Language: C++
    Result: Accepted
    Time:156 ms
    Memory:3172 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
int sr, sb, sg, m, p;
int pow_mod(int a, int b) {
  int ans = 1, res = a;
  while(b) {
    if(1 & b) ans = (ans * res) % p;
    res = (res * res) % p; b >>= 1;
  }
  return ans;
}
int inv(int x) {
  return pow_mod(x % p, p - 2);
}
 
int d[65][21][21][21];
std::vector<int> len;
int dp() {
  int n = len.size();
  d[0][0][0][0] = 1;
  for(int i = 1; i <= n; i ++) {
    int l = len[i - 1];
    for(int j = 0; j <= sr; j ++) {
      for(int k = 0; k <= sb; k ++) {
        for(int t = 0; t <= sg; t ++) {
          d[i][j][k][t] = 0;
          if(j >= l) d[i][j][k][t] += d[i - 1][j - l][k][t];
          if(k >= l) d[i][j][k][t] += d[i - 1][j][k - l][t];
          if(t >= l) d[i][j][k][t] += d[i - 1][j][k][t - l];
          d[i][j][k][t] %= p;
        }
      }
    }
  }
  return d[n][sr][sb][sg];
}
 
int next[65]; bool vis[65];
int main() {
  scanf("%d%d%d%d%d", &sr, &sb, &sg, &m, &p);
  int n = sr + sb + sg;
  int ans = 0;
  for(int i = 1; i <= n; i ++) {
    len.push_back(1);
  }
  ans = dp();
  for(int i = 1; i <= m; i ++) {
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i ++) {
      scanf("%d", &next[i]);
    }
    len.clear();
    for(int i = 1; i <= n; i ++) {
      if(!vis[i]) {
        int p = i, cnt = 0;
        do {
          vis[p] = true; cnt ++;
          p = next[p];
        } while(p != i);
        len.push_back(cnt);
      }
    }
    ans = (ans + dp()) % p;
  }
  ans = (ans * inv(m + 1)) % p;
  printf("%d\n", ans);
  return 0;
}

[BZOJ 3640]JC的小苹果

逆矩阵文明,,,

很显然我们可以定义一个状态\(f[i][j]\)表示当前血量为\(i\)走到\(j\)的概率,然后肥肠爆歉这个东西没法DP(可能会有的点的伤害为0,这样可以凿出来环)。考虑高消,这个东西有个好处是不可能从血量低的到血量高的状态,所以可以从大到小枚举血量,这样各层事独立的,复杂度比直接高消降低了很少。可惜复杂度为\(O(sn^3)\)(设血量为\(s\)),会T掉。

考虑转移的过程,转移时等价于解这样一个方程:

\[
\begin{aligned}
a_{11}x_{1} + a_{12}x_{2} + \ldots + a_{1n}x_{n} &= c_1\\
a_{21}x_{1} + a_{22}x_{2} + \ldots + a_{2n}x_{n} &= c_2\\
&\ldots\\
a_{n1}x_{1} + a_{n2}x_{2} + \ldots + a_{nn}x_{n} &= c_n
\end{aligned}
\]

其中的未知数\(x\)事我们要求的东西,\(c\)表示从高血量状态转移过来的概率(这个可以视作常数)。根据友矩阵那一套理论,这一系列方程等价于以下等式:

\[
\begin{bmatrix}
a_{11} & a_{12} & \ldots & a_{1n}\\
a_{21} & a_{22} & \ldots & a_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n1} & a_{n2} & \ldots & a_{nn}
\end{bmatrix}
\begin{bmatrix}
x_{1}\\ x_{2} \\ \vdots \\ x_{n}
\end{bmatrix}
=
\begin{bmatrix}
c_1\\ c_2\\ \vdots\\ c_n
\end{bmatrix}
\]

不妨将之简记为\(AB = C\),其中我们只有\(B\)不知道,要求的也是\(B\)。我们除一下就可以得到\(B = A^{-1}C\),然后我们还发现每一层的\(A\)都是一样的,所以每一层的\(A^{-1}\)也都是一样的,预处理即可。这样转移部分的复杂度就变成了\(O(sn^2)\)(矩阵乘法在这里事方阵乘列向量)。

至于逆矩阵的求法,我们知道对矩阵做初等变化也就等价于乘上另一个矩阵。因此,我们将一个矩阵\(A\)用类似于高消的手段消为单位阵\(I\),所做的初等变换也就等价于乘上\(A^{-1}\)。我们对一个单位阵\(I\)作用上一样的操作,也就等于给这个单位阵乘上了\(A^{-1}\),这样我们就得到了\(A^{-1}\)。

代码:

/**************************************************************
    Problem: 3640
    User: danihao123
    Language: C++
    Result: Accepted
    Time:8708 ms
    Memory:13416 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#include <map>
int n, m, hp;
const int maxn = 151, maxm = 5005;
const int maxh = 10005;
typedef double R;
typedef R Mat[maxn][maxn];
Mat D, F;
void calc_inv() {
  for(int i = 1; i <= n; i ++) {
    F[i][i] = 1;
  }
  for(int i = 1; i <= n; i ++) {
    int r = i;
    for(int j = i + 1; j <= n; j ++) {
      if(fabs(D[j][i]) > fabs(D[r][i])) {
        r = j;
      }
    }
    // assert(r > -1);
    if(r != i) {
      for(int j = 1; j <= n; j ++) {
        std::swap(D[r][j], D[i][j]);
        std::swap(F[r][j], F[i][j]);
      }
    }
    R bs = D[i][i];
    for(int j = 1; j <= n; j ++) {
      D[i][j] /= bs; F[i][j] /= bs;
    }
    for(int k = 1; k <= n; k ++) {
      if(k != i) {
        R rate = D[k][i];
        for(int j = 1; j <= n; j ++) {
          D[k][j] -= rate * D[i][j];
          F[k][j] -= rate * F[i][j];
        }
      }
    }
  }
}
void matrix_mul(const Mat &A, const Mat &B, int a, int b, int c, Mat &res) {
  static Mat C;
  for(int i = 1; i <= a; i ++) {
    for(int j = 1; j <= c; j ++) {
      C[i][j] = 0;
    }
  }
  for(int i = 1; i <= a; i ++) {
    for(int j = 1; j <= c; j ++) {
      for(int k = 1; k <= b; k ++) {
        C[i][j] += A[i][k] * B[k][j];
      }
    }
  }
  for(int i = 1; i <= a; i ++) {
    for(int j = 1; j <= c; j ++) {
      res[i][j] = C[i][j];
    }
  }
}
 
int first[maxn], deg[maxn];
int next[maxm << 1], to[maxm << 1];
int gcnt = 0;
void add_edge(int u, int v) {
  gcnt ++;
  next[gcnt] = first[u]; first[u] = gcnt;
  to[gcnt] = v;
}
void ins_edge(int u, int v) {
  deg[u] ++;
  add_edge(u, v);
  if(u != v) {
    deg[v] ++;
    add_edge(v, u);
  }
}
 
int atk[maxn];
R f[maxh][maxn];
R solve() {
  for(int i = 1; i <= n; i ++) {
    D[i][i] = 1.00;
  }
  for(int i = 1; i < n; i ++) {
    for(int j = first[i]; j; j = next[j]) {
      int v = to[j];
      if(!atk[v]) {
        D[v][i] -= 1.00 / (R(deg[i]));
      }
    }
  }
  calc_inv();
  R ans = 0; static Mat C;
  f[hp][1] = 1.00;
  for(int i = hp; i >= 1; i --) {
    for(int j = 1; j <= n; j ++) {
      C[j][1] = f[i][j];
    }
    matrix_mul(F, C, n, n, 1, C);
    for(int j = 1; j < n; j ++) {
      for(int e = first[j]; e; e = next[e]) {
        int v = to[e];
        if(atk[v] > 0 && i - atk[v] > 0) {
          f[i - atk[v]][v] += C[j][1] / (R(deg[j]));
        }
      }
    }
    ans += C[n][1];
  }
  return ans;
}
 
int main() {
  scanf("%d%d%d", &n, &m, &hp);
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &atk[i]);
  }
  for(int i = 1; i <= m; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    ins_edge(u, v);
  }
  printf("%.8lf\n", solve());
  return 0;
}

[LibreOJ 2383][HNOI2013]游走

本野蛮人竟然没做过高消期望DP,,,泪,流了下来,,,

根据期望线性性,答案就是所有边的期望被走的次数乘上边的编号的和。一条边期望经过的次数可以根据他两个端点期望经过的次数来算(但是\(n\)要特判一下),要求所有点期望走过的次数当然就可以列\(n\)个方程然后高消力。然后期望走的次数多的边编号应该小,反之亦然,所以求完每条边走的次数的期望之后就贪心一下就好力。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <utility>
#include <cmath>
const int maxn = 505;
const int maxm = maxn * maxn;
using R = double;
const R eps = 1e-9;
int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    return ((x < 0.00) ? -1 : 1);
  }
}
R D[maxn][maxn];
int n;
void gauss() {
#ifdef LOCAL
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n + 1; j ++) {
      printf("%.3lf ", D[i][j]);
    }
    puts("");
  }
#endif
  for(int i = 1; i <= n; i ++) {
    int r = i;
    for(int j = i + 1; j <= n; j ++) {
      if(fabs(D[j][i]) > fabs(D[r][i])) {
        r = j;
      }
    }
    assert(sign(D[r][i]) != 0);
    if(r != i) {
      for(int j = 1; j <= n + 1; j ++) {
        std::swap(D[i][j], D[r][j]);
      }
    }
    for(int k = i + 1; k <= n; k ++) {
      R rate = D[k][i] / D[i][i];
      for(int j = i; j <= n + 1; j ++) {
        D[k][j] -= D[i][j] * rate;
      }
    }
  }
  for(int i = n; i >= 1; i --) {
    for(int j = i + 1; j <= n; j ++) {
      D[i][n + 1] -= D[j][n + 1] * D[i][j];
      D[i][j] = 0;
    }
    D[i][n + 1] /= D[i][i]; D[i][i] = 1;
#ifdef LOCAL
    printf("E[%d] : %.3lf\n", i, D[i][n + 1]);
#endif
  }
}

int E[maxm][2], deg[maxn];
R tms[maxm];
void add_edge(int u, int v) {
  if(u != n) D[v][u] += 1.00 / (R(deg[u]));
}

int main() {
  int m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i ++) {
    D[i][i] = -1;
  }
  D[1][n + 1] = -1;
  for(int i = 1; i <= m; i ++) {
    scanf("%d%d", &E[i][0], &E[i][1]);
    deg[E[i][0]] ++; deg[E[i][1]] ++;
  }
  for(int i = 1; i <= m; i ++) {
    int u = E[i][0], v = E[i][1];
    add_edge(u, v); add_edge(v, u);
  }
  gauss();
  for(int i = 1; i <= m; i ++) {
    tms[i] = 0;
    int u = E[i][0], v = E[i][1];
    if(u != n) tms[i] += D[u][n + 1] / (R(deg[u]));
    if(v != n) tms[i] += D[v][n + 1] / (R(deg[v]));
  }
  std::sort(tms + 1, tms + 1 + m, [&](const R &i, const R &j) { return i > j; });
  R ans = 0;
  for(int i = 1; i <= m; i ++) {
    ans += tms[i] * (R(i));
  }
  printf("%.3lf\n", ans);
  return 0;
}