[BZOJ 4816][SDOI2017]数字表格

当年在考场上一点反演都不会啊啊啊啊啊啊

这题虽然牵扯到了对积的反演,但其实也不是很难。先让我们大力推导一波(逃

考虑枚举柿子中的\(f[(i, j)]\)中的最大公约数(设为\(k\)),然后式子变成了(这里不妨偷个懒,钦定\(n\leq m\)):

\[\prod_{k = 1}^n f[k]^{\sum_{i = 1}^n \sum_{j = 1}^m\:[(i, j) = k]}\]

然后发现上面那个指数就是Problem b的式子,显然可化为\(\sum_{d = 1}^n \mu(d) \lfloor\frac{n}{kd}\rfloor \lfloor\frac{m}{kd}\rfloor\)。然后似乎化简没有余地了,但是根据直觉,我们可以钦定\(T = kd\),然后枚举\(T\)。

然后柿子变成了:

\[\prod_{T = 1}^n (\prod_{k\mid T} f[k]^{\mu(\tfrac{T}{k})})^{\lfloor\tfrac{n}{T}\rfloor \lfloor\tfrac{m}{T}\rfloor}\]

柿子中的\(\prod_{k\mid T} f[k]^{\mu(\tfrac{T}{k})}\)是一个类似狄利克雷卷积的东西(取完对数就是了),可以枚举约数预处理。并且这个东西很不错的一点就是上面的指数是莫比乌斯函数,可以取到的值只有那三种,不需要快速幂。

然后剩下的部分就和通常的反演题一般无二了……

代码(卡线过的蒟蒻……求轻喷……但我在LOJ上跑的还挺快的):

/**************************************************************
    Problem: 4816
    User: danihao123
    Language: C++
    Result: Accepted
    Time:50840 ms
    Memory:33048 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <cctype>
#include <cassert>
const int N = 1000000;
const int maxn = N + 5;
typedef long long ll;
const ll ha = 1000000007LL;
bool p_flag = false;
ll pow_mod(ll a, ll b) {
  if(!b) return 1LL;
  ll ans = pow_mod(a, b / 2LL);
  ans = (ans * ans) % ha;
  if(1LL & b) ans = (ans * a) % ha;
#ifdef LOCAL
  if(p_flag) printf("%lld^%lld : %lld\n", a, b, ans);
  if(b == ha - 2LL) p_flag = false;
#endif
  return ans;
}
ll inv(ll x) {
  // if(x == 1LL) p_flag = true;
  return pow_mod(x, ha - 2LL);
}
int miu[maxn];
void sieve() {
  static int prm[maxn]; int cnt = 0;
  static bool vis[maxn];
  miu[1] = 1;
  for(int i = 2; i <= N; i ++) {
    if(!vis[i]) {
      miu[i] = -1;
      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;
      }
    }
  }
}
ll f[maxn], inv_d[maxn], F[maxn];
void process() {
  sieve();
  f[1] = 1LL; inv_d[1] = 1LL;
  for(int i = 2; i <= N; i ++) {
    f[i] = (f[i - 1] + f[i - 2]) % ha;
    inv_d[i] = inv(f[i]);
    assert(f[i] != 0LL); assert(inv_d[i] != 0LL);
  }
  for(int i = 1; i <= N; i ++) F[i] = 1LL;
  for(int i = 1; i <= N; i ++) {
    for(int j = i; j <= N; j += i) {
      int res = j / i;
      if(miu[res] == 1) {
        F[j] = (F[j] * f[i]) % ha;
#ifdef LOCAL
        if(j <= 3) printf("f[%d](%lld) -> F[%d]\n", i, f[i], j);
#endif
        continue;
      }
      if(miu[res] == -1) {
        F[j] = (F[j] * inv_d[i]) % ha;
#ifdef LOCAL
        if(j <= 3) printf("inv_f[%d](%lld) -> F[%d]\n", i, inv_d[i], j);
#endif
      }
    }
  }
  F[0] = 1LL;
  bool flag = true;
  for(int i = 1; i <= N; i ++) {
    F[i] = (F[i] * F[i - 1]) % ha;
    if(flag && F[i] == 0LL) {
      printf("SF[%d] has been 0.\n", i);
      flag = false;
    }
  }
}
 
ll calc(ll n, ll m) {
  if(n > m) std::swap(n, m);
  ll ans = 1LL;
  for(ll i = 1; i <= n;) {
    ll nx = std::min(n / (n / i), m / (m / i));
#ifdef LOCAL
    // printf("nx of %lld : %lld\n", i, nx);
#endif
    ll mulv = pow_mod((F[nx] * inv(F[i - 1])) % ha, (n / i) * (m / i));
    ans = (ans * mulv) % ha;
    i = nx + 1LL;
  }
  return ans;
}
 
int main() {
  process();
  int T; scanf("%d", &T);
  while(T --) {
    int n, m; scanf("%d%d", &n, &m);
    printf("%lld\n", calc(n, m));
  }
  return 0;
}

[BZOJ 5059]前鬼后鬼的守护

这不是可并堆裸题吗……我这种傻逼只会用线段树合并做

显然一个集合的中位数可以用平衡树或者权值线段树求出,然后为了方便合并我用了权值线段树。

然后考虑对于一个递减的序列,选择中位数一定更优,一个递增的序列当然xjb选即可。我们可以用一个栈来维护当前的所有答案区间,然后考虑一个新的点加进来。这个点的答案如果比栈首答案小,那么就违反了单调不降的要求,我们需要把两段合并。然后完了……

代码:

/**************************************************************
	Problem: 5059
	User: danihao123
	Language: C++
	Result: Accepted
	Time:2348 ms
	Memory:250520 kb
****************************************************************/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <algorithm>
#include <utility>
#include <stack>
const int BUFSIZE = 20 * 1024 * 1024;
int n;
struct Node {
  Node *lc, *rc;
  int sumv;
};
Node pool[BUFSIZE];
Node *nil, *cur;
void init_pool() {
  cur = nil = pool;
  nil -> lc = nil -> rc = nil;
  nil -> sumv = 0;
}
Node *alloc_node(int v = 0, Node *lc = nil, Node *rc = nil) {
  cur ++;
  cur -> lc = lc; cur -> rc = rc;
  cur -> sumv = v;
  return cur;
}
void modify(Node* &o, int L, int R, int p, int v) {
  if(o == nil) {
    o = alloc_node(0);
  }
  o -> sumv += v;
  if(L < R) {
    int M = (L + R) / 2;
    if(p <= M) {
      modify(o -> lc, L, M, p, v);
    } else {
      modify(o -> rc, M + 1, R, p, v);
    }
  }
}
Node *merge(Node* &tag, Node* &src) {
  if(src == nil) return tag;
  if(tag == nil) {
    return src;
  }
  tag -> sumv += src -> sumv;
  tag -> lc = merge(tag -> lc, src -> lc);
  tag -> rc = merge(tag -> rc, src -> rc);
  return tag;
}
int kth(Node *o, int L, int R, int k) {
  if(L == R) {
    return L;
  } else {
    int M = (L + R) / 2;
    if(k <= o -> lc -> sumv) {
      return kth(o -> lc, L, M, k);
    } else {
      return kth(o -> rc, M + 1, R, k - o -> lc -> sumv);
    }
  }
}
void gou_tree(Node *o, int L, int R) {
  printf("Tree (%d, %d, %d)\n", L, R, o -> sumv);
  int M = (L + R) / 2;
  if(L < R) {
    gou_tree(o -> lc, L, M);
    gou_tree(o -> rc, M + 1, R);
  }
}
int lsiz;
const int maxn = 500005;
int A[maxn], A2[maxn];
void break_up() {
  std::sort(A2 + 1, A2 + 1 + n);
  lsiz = std::unique(A2 + 1, A2 + 1 + n) - A2 - 1;
  for(int i = 1; i <= n; i ++) {
    A[i] = std::lower_bound(A2 + 1, A2 + 1 + lsiz, A[i]) - A2;
  }
}
struct Interval {
  Node *rt;
  int l, r; int siz, ans;
  Interval() {
    rt = nil;
    siz = ans = 0;
  }
  Interval(int p) {
    rt = nil; modify(rt, 1, lsiz, p, 1);
    siz = 1; ans = p;
  }
};
typedef long long ll;
ll solve() {
  break_up(); init_pool();
  std::stack<Interval> S;
  for(int i = 1; i <= n; i ++) {
    Interval nv(A[i]);
    nv.l = nv.r = i;
    while(!S.empty() && S.top().ans > nv.ans) {
      Interval g = S.top(); S.pop();
#ifdef LOCAL
    printf("ans of [%d, %d] : %d\n", g.l, g.r, A2[g.ans]);
#endif
      nv.l = g.l; nv.siz += g.siz;
      nv.rt = merge(nv.rt, g.rt);
#ifdef LOCAL
      gou_tree(nv.rt, 1, lsiz);
#endif
      nv.ans = kth(nv.rt, 1, lsiz, (nv.siz + 1) / 2);
    }
    S.push(nv);
  }
  ll ans = 0;
  while(!S.empty()) {
    Interval g = S.top(); S.pop();
#ifdef LOCAL
    printf("ans of [%d, %d] : %d\n", g.l, g.r, A2[g.ans]);
#endif
    for(int i = g.l; i <= g.r; i ++) {
      ans += abs(A2[A[i]] - A2[g.ans]);
    }
  }
  return ans;
}

int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &A[i]);
    A2[i] = A[i];
  }
  printf("%lld\n", solve());
  return 0;
}

[BZOJ 3527][ZJOI2014]力

现在才明白卷积真的是the deep, dark fantasies……(逃

首先约去\(q_i\),得到:

\[E_j = \sum_{i < j}\frac{q_i}{(j - i)^2} - \sum_{j < i}\frac{q_i}{(j - i)^2}\]

注意到如果很容易得到等式前半部分的高效求法,后半部分把序列反过来就能做了。

那么我们会发现,设\(g_x = \frac{1}{x^2}\),然后式子前半部分(姑且称作\(p_j\))可表示为:

\[p_j = \sum_{i < j} q_i g_{j - i}\]

这不就是个卷积吗?FFT一波即可。

代码:

/**************************************************************
    Problem: 3527
    User: danihao123
    Language: C++
    Result: Accepted
    Time:9984 ms
    Memory:28952 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <cassert>
#include <complex>
typedef long double R;
typedef std::complex<R> C;
const R eps = 1e-3;
int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    if(x < 0) {
      return -1;
    } else {
      return 1;
    }
  }
}
const int maxn = 400005;
const double pi = acos(-1);
int bi, len;
int flip(int x) {
  int ans = 0;
  for(int i = 0; i < bi; i ++) {
    if(x & (1 << i)) {
      ans += 1 << (bi - i - 1);
    }
  }
  return ans;
}
void fft(C *A, double g = 1) {
  for(int i = 0; i < len; i ++) {
    int R = flip(i);
#ifdef LOCAL
    // printf("The flipping of %d is %d\n", i, R);
#endif
    if(i < R) {
      std::swap(A[R], A[i]);
    }
  }
  for(int L = 1; L < len; L <<= 1) {
    C xi_n(cos(pi / (double(L))), sin(g * pi / (double(L))));
    for(int i = 0; i < len; i += L << 1) {
      C xi(1, 0);
      for(int j = i; j < i + L; j ++) {
        C a = A[j], b = A[j + L];
        A[j] = a + xi * b;
        A[j + L] = a - xi * b;
        xi = xi * xi_n;
      }
    }
  }
}
 
int main() {
  int n;
  static C A[maxn], rd[maxn]; static R ans[maxn];
  static R q[maxn];
  scanf("%d", &n);
  bi = 0; len = 1;
  while(len <= 2 * n) {
    len <<= 1;
    bi ++;
  }
  for(int i = 0; i < n; i ++) {
    scanf("%Lf", &q[i]); A[i] = q[i];
  }
  assert(sign(rd[0].real()) == 0);
  for(int i = 1; i < n; i ++) {
    rd[i] = 1.00 / ((R(i)) * (R(i)));
#ifdef LOCAL
    printf("rd[%d] : %.5Lf\n", i, rd[i].real());
#endif
  }
  fft(A); fft(rd);
  for(int i = 0; i < len; i ++) A[i] *= rd[i];
  fft(A, -1);
  for(int i = 0; i < n; i ++) {
    ans[i] += A[i].real() / len;
#ifdef LOCAL
    printf("delta_v of %d : %.5Lf\n", i, A[i].real() / len);
#endif
  }
  std::reverse(q, q + n);
  for(int i = 0; i < len; i ++) A[i] = 0;
  for(int i = 0; i < n; i ++) {
    A[i] = q[i];
  }
  fft(A);
  for(int i = 0; i < len; i ++) A[i] *= rd[i];
  fft(A, -1);
  for(int i = 0; i < n; i ++) {
    ans[i] -= A[n - 1 - i].real() / len;
    printf("%.3Lf\n", ans[i]);
  }
  return 0;
}

[BZOJ 3992][SDOI2015]序列统计

终于调过去了……(然而不就是道NTT+生成函数水题吗至于调半天)

首先积非常的恶心,考虑转成和。这个事需要求指标的……求指标的话枚举原根的若干次幂即可(恰好$m$是素数一定有原根……),判断原根用比较大力的手段即可(我搞了一个$O(n\sqrt{n}logn)$的……求轻喷)。

然后这题还算比较简单吧……用生成函数表示原来的集合,然后$n$次幂就可以了。

注意那事个循环卷积……所以要开两倍然后每次乘完了再把右半部分搞过去。

代码:

/**************************************************************
    Problem: 3992
    User: danihao123
    Language: C++
    Result: Accepted
    Time:6652 ms
    Memory:1864 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>
#include <cmath>
typedef long long ll;
const int maxn = 32005;
const ll ha = 1004535809LL;
const ll bs = 3LL;
ll n, m, gl; int sz;
ll pow_mod(ll a, ll b, ll p) {
  if(!b) return 1LL;
  ll ans = pow_mod(a, b >> 1, p);
  ans = (ans * ans) % p;
  if(b & 1LL) ans = (ans * a) % p;
  return ans;
}
ll inv(ll x, ll p) {
  return pow_mod(x, p - 2LL, p);
}
void break_up(ll x, std::vector<ll> &V) {
  int bd = sqrt(x + 0.5);
  for(ll i = 2; i <= bd; i ++) {
    if(x % i == 0) {
      V.push_back(i);
      while(x % i == 0) x /= i;
    }
    if(x == 1LL) break;
  }
  if(x > 1LL) V.push_back(x);
}
ll get_phi() {
  if(m == 2LL) return 1LL;
  ll mi = m - 1LL;
  std::vector<ll> V;
  break_up(mi, V);
  for(ll i = 2; i <= mi; i ++) {
    bool ok = true;
    for(int j = 0; j < V.size(); j ++) {
      ll b = mi / V[j];
      if(pow_mod(i, b, m) == 1LL) {
        ok = false;
#ifdef LOCAL
        printf("%lld not passed!\n", i);
#endif
        break;
      }
    }
    if(ok) {
      return i;
    }
  }
}
 
int bi, len;
int flip(int x) {
  int ans = 0;
  for(int i = 0; i < bi; i ++) {
    if((1 << i) & x) {
      ans += (1 << (bi - i - 1));
    }
  }
  return ans;
}
void ntt(ll *A, bool flag = false) {
  for(int i = 0; i < len; i ++) {
    int v = flip(i);
    if(v < i) std::swap(A[i], A[v]);
  }
  for(int L = 1; L < len; L <<= 1) {
    ll xi_n = pow_mod(3LL, (ha - 1LL) / (ll(L << 1)), ha);
    if(flag) xi_n = inv(xi_n, ha);
    for(int i = 0; i < len; i += (L << 1)) {
      ll w = 1;
      for(int j = i; j < i + L; j ++) {
        ll p1 = A[j], p2 = A[j + L];
        A[j] = (p1 + (p2 * w) % ha) % ha;
        A[j + L] = (p1 - (p2 * w) % ha + ha) % ha;
        w = (w * xi_n) % ha;
      }
    }
  }
}
void poly_mul(ll *A, ll *B) {
  static ll C[maxn]; memset(C, 0, sizeof(C));
#ifdef LOCAL
  printf("A :");
  for(int i = 0; i < len; i ++) printf(" %lld", A[i]);
  puts("");
  printf("B :");
  for(int i = 0; i < len; i ++) printf(" %lld", B[i]);
  puts("");
#endif
  ntt(A); ntt(B);
  for(int i = 0; i < len; i ++) C[i] = (A[i] * B[i]) % ha;
  ntt(C, true);
  ll inv_n = inv(len, ha);
  for(int i = 0; i < len; i ++) {
    C[i] = (C[i] * inv_n) % ha;
  }
#ifdef LOCAL
  printf("C (not processed) :");
  for(int i = 0; i < len; i ++) printf(" %lld", C[i]);
  puts("");
#endif
  for(int i = 0; i < len; i ++) {
    int v = i % (m - 1LL);
    if(v != i) {
      C[v] = (C[v] + C[i]) % ha;
      C[i] = 0LL;
    }
  }
#ifdef LOCAL
  printf("C :");
  for(int i = 0; i < len; i ++) printf(" %lld", C[i]);
  puts("");
#endif
  std::copy(C, C + len, A);
}
void poly_pow(ll *A, ll b) {
  static ll B[maxn];
  static ll res[maxn];
  std::copy(A, A + len, res);
  std::fill(A, A + len, 0); A[0] = 1LL;
#ifdef LOCAL
  printf("A :");
  for(int i = 0; i < len; i ++) printf(" %lld", A[i]);
  puts("");
  printf("res : ");
  for(int i = 0; i < len; i ++) printf("%lld ", res[i]);
  puts("");
#endif
  while(b) {
    if(1LL & b) {
      std::copy(res, res + len, B);
      poly_mul(A, B);
      std::fill(B, B + len, 0);
    }
    std::copy(res, res + len, B);
    poly_mul(res, B);
    std::fill(B, B + len, 0);
    b >>= 1LL;
  }
}
 
int main() {
  static bool vis[maxn];
  static ll A[maxn];
  scanf("%lld%lld%lld%d", &n, &m, &gl, &sz);
  ll phi = get_phi();
  for(int i = 1; i <= sz; i ++) {
    int v; scanf("%d", &v);
    if(v == 0) continue;
    vis[v] = true;
  }
  int logx = 0;
  bi = 0; len = 1;
  while(len <= (2 * m - 2)) {
    bi ++; len <<= 1;
  }
  for(int i = 0; i < (m - 1); i ++) {
    int v = pow_mod(phi, i, m);
    if(vis[v]) {
      A[i] ++;
#ifdef LOCAL
      printf("log(%d) : %d\n", v, i);
#endif
    }
    if(v == gl) {
      logx = i;
    }
  }
  poly_pow(A, n);
  printf("%lld\n", A[logx]);
  return 0;
}

[BZOJ 2115][Wc2011]Xor

这个可以有啊(赞赏)!

我们可以发现如果两点间如果有多条路径,那么任意两条路径在一个简单环里。

然后我们还发现,如果说是一个路径,一个环和这个路径有交边,那么走这个环走很多次没有意义(其实相当于从环的两边选一边走)。

然后这样可以发现,用$1$到$n$的路径来异或一个环,可以得到新的一条$1$到$n$的路径。

这样我们可以用DFS树来求出图上所有简单环的异或和,求出其线性基,然后随便找条$1$到$n$的路径,问题就变成了求这条路径和那个线性基的异或和最大是多少。然后这就是线性基乱搞好了……

代码:

/**************************************************************
    Problem: 2115
    User: danihao123
    Language: C++
    Result: Accepted
    Time:652 ms
    Memory:6544 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <vector>
typedef long long ll;
const int maxn = 50005;
const int maxm = maxn << 2;
int first[maxn];
int next[maxm], to[maxm];
ll dist[maxm]; int rev[maxm];
int add_edge(int u, int v, ll d) {
  static int cnt = 0;
  cnt ++;
  next[cnt] = first[u]; first[u] = cnt;
  to[cnt] = v; dist[cnt] = d;
  return cnt;
}
void ins_edge(int u, int v, ll d) {
  int e1 = add_edge(u, v, d);
  int e2 = add_edge(v, u, d);
  rev[e1] = e2; rev[e2] = e1;
}
 
const int maxb = 61;
ll T[maxb];
void insert(ll x) {
  for(int i = 60; i >= 0; i --) {
    if(!x) break;
    if((x & (1LL << i)) == 0) continue;
    if(T[i]) {
      x ^= T[i];
    } else {
      for(int j = i - 1; j >= 0; j --) {
        if(x & (1LL << j)) {
          x ^= T[j];
        }
      }
      for(int j = i + 1; j < maxb; j ++) {
        if(T[j] & (1LL << i)) {
          T[j] ^= x;
        }
      }
      T[i] = x; break;
    }
  }
}
ll sum[maxn];
bool vis[maxn], used[maxm];
void dfs(int x, ll s) {
  vis[x] = true; sum[x] = s;
  for(int i = first[x]; i; i = next[i]) {
    if(used[i]) continue;
    int v = to[i];
    used[i] = used[rev[i]] = true;
    if(vis[v]) {
      insert((s ^ sum[v]) ^ dist[i]);
    } else {
      dfs(v, s ^ dist[i]);
    }
  }
}
 
#ifdef LOCAL
#define LO "%I64d"
#else
#define LO "%lld"
#endif
int main() {
  int n, m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int u, v; ll d;
    scanf("%d%d", &u, &v); scanf(LO, &d);
    ins_edge(u, v, d);
  }
  dfs(1, 0LL);
  ll ret = sum[n];
  for(int i = 60; i >= 0; i --) {
    if(!T[i]) continue;
    if(!(ret & (1LL << i))) {
      ret ^= T[i];
    }
  }
  printf(LO, ret); puts("");
  return 0;
}

[LibreOJ 114]k大异或和

最近学了一点线性基……所以也就做了一些线性基的题目

这题还算挺简单的吧……先转成求第$s - k + 1$(这里用$s$表示异或和有多少种)大。求出线性基,然后从高位向低位枚举,然后乱搞就行……

唯一的坑就是子集要求非空。这样有可能会出现选不出$0$的情况,但是稍微思索一下可以发现如果$|B| < n$(这里用$B$表示线性基)那么一定可以用$B$里的东西凑出来一个数,然后再和不在线性基里的一个数异或一下,这样就能搞出来$0$了。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
using ll = long long int;
const int maxb = 51;
ll T[maxb];
void insert(ll x) {
  for(int i = 50; i >= 0; i --) {
    if(!x) break;
    if((x & (1LL << i)) == 0) continue;
    if(T[i]) {
      x ^= T[i];
    } else {
      for(int j = i - 1; j >= 0; j --) {
        if(x & (1LL << j)) {
          x ^= T[j];
        }
      }
      for(int j = i + 1; j < maxb; j ++) {
        if(T[j] & (1LL << i)) {
          T[j] ^= x;
        }
      }
      T[i] = x; break;
    }
  }
}

#ifdef LOCAL
#define LO "%I64d"
#else
#define LO "%lld"
#endif
int main() {
  int sz = 0;
  ll tot = 0;
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    ll x; scanf(LO, &x);
    insert(x);
  }
  for(int i = 0; i < maxb; i ++) if(T[i]) sz ++;
  tot = (1LL << sz) - 1LL;
  if(sz < n) tot ++;
  int m; scanf("%d", &m);
  while(m --) {
    ll k; scanf(LO, &k);
    if(k <= 0LL || k > tot) {
      puts("-1");
    } else if(sz < n && k == 1LL) {
      puts("0");
    } else {
      k = tot - k + 1LL;
      int rest = sz; ll ret = 0;
      for(int i = 50; i >= 0; i --) {
        if(!T[i]) continue;
        rest --;
        if(k <= (1LL << rest)) {
          ret ^= T[i];
        } else {
          k -= (1LL << rest);
        }
      }
      printf(LO, ret); puts("");
    }
  }
  return 0;
}

[BZOJ 2876][NOI2012]骑行川藏

我终于A了……不就是拉格朗日乘数法的模板题吗

首先这道题最优情况下一定有(这里用\(E_i\)表示第\(i\)段路程的耗能):\(\sum_{i = 1}^n E_i = E_u\)。

然后这个东西是一个等式限制条件,然后我们还要最小化总用时,给人拉格朗日乘数法的即视感……

不管怎么说让我们来列式子吧:

\[h(x_1, x_2,\ldots ,x_n, \lambda) = \sum_{i = 1}^n \frac{s_i}{x_i} + \lambda \sum_{i = 1}^n k_i s_i (x_i - v_i)^2\]

\[\frac{\partial h}{\partial x_i} = -\frac{s_i}{x_i^2} + 2\lambda k_i s_i (x_i - v_i)\]

然后你会想这TM怎么解方程……

但是我们想一想,把\(\frac{\partial h}{\partial x_i} = 0\)稍作整理,得:

\[\frac{1}{2k_i\lambda} = x_i^2 (x_i - v_i)\]

对于式子的左边,是一个关于\(x_i\)的增函数(因为这道题默认了\(x_i\geq 0\)且\(x_i\geq v_i\)),然后不妨令\(\frac{1}{\lambda} = u\),可以发现\(u\)越大则\(x_i\)越大!这样一来那么我们的限制条件就会更加难以满足。

所以我们可以二分这个\(u\)来解这些方程。

BTW,这题卡精度非常厉害……

代码:

/**************************************************************
    Problem: 2876
    User: danihao123
    Language: C++
    Result: Accepted
    Time:3960 ms
    Memory:1524 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <cassert>
typedef double R;
const R eps = 1e-12;
const int maxn = 10005;
int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    if(x < 0) {
      return -1;
    } else {
      return 1;
    }
  }
}
R s[maxn], k[maxn], V[maxn];
R rf(int i, R v, R delta) {
  return v * v * (v - V[i]) - delta;
}
R rf2(int i, R v) {
  return 3 * v * v - 2 * v * V[i];
}
R gen_rt(int i, R delta) {
  R x = 1e6;
  int lambda = 100;
  while(lambda --) {
    R a = rf(i, x, delta);
    if(sign(a) == 0) break;
    R da = rf2(i, x);
    x -= a / da;
  }
  return x;
}
int n; R E;
R gen_lft() {
  R l = 1e-14, r = 1e16;
  while(r - l > eps) {
#ifdef LOCAL
    printf("State [%.18lf, %.18lf]\n", l, r);
#endif
    R M = (l + r) / 2;
    R T = 0;
    for(int i = 1; i <= n; i ++) {
      R v = gen_rt(i, M / (2 * k[i]));
      T += (v - V[i]) * (v - V[i]) * k[i] * s[i];
    }
    if(sign(T - E) <= 0) {
      l = M;
    } else {
      r = M;
    }
  }
  return l;
}
 
int main() {
  std::cin >> n >> E;
  for(int i = 1; i <= n; i ++) {
    std::cin >> s[i] >> k[i] >> V[i];
  }
  R M = gen_lft();
  R tm = 0;
  for(int i = 1; i <= n; i ++) {
    R v = gen_rt(i, M / (2 * k[i]));
    tm += s[i] / v;
  }
  printf("%.8lf\n", tm);
  return 0;
}

[LibreOJ 2135][ZJOI2015]幻想乡战略游戏

竟然1A了蛤蛤蛤蛤蛤

这题用人话说就是给你一个不会动的树,让你求带权重心。

先解决一个问题:如果要求动态修改点权,并且要求多次询问求某点\(x\)的\(\sum_{i = 1}^n d_i\cdot dist(i, x)\),怎么做?

很显然对于一个点\(x\),对它造成贡献的点,可能是在以\(x\)为根的点分子树里的,也可能在\(x\)之外。但是一个不在该点分子树内的点要对\(x\)产生贡献,必须要经过\(x\)在分治树上的祖先。

所以我们可以考虑对每个重心,记录下它这个点分子树中所有点对该重心的贡献、对点分树上的父亲的贡献以及该点分子树的点权和。每次求答案时\(x\)所在的分治子树的贡献很好考虑,那考虑一下其分治树上祖先对\(x\)的贡献就行了。

那带权重心怎么求呢?如果我们把树的根变成带权重心,那么我们会发现越远离根则答案越劣。所以我们如果只往使得答案更小的地方走,那么最后一定会走到带权重心上。

我们考虑把这个过程放点分树上。从整棵树的重心开始往下走,每次如果发现有一条出边指向的点答案更好,那就往这个子结构(不是指向的点而是那个联通块的重心,否则时间复杂度不对)里走。最后走不动了,走到的点就是带权重心了。

求LCA我用的是\(O(logn)\)的树剖而不是\(O(1)\)搞法,但是跑的贼快(可能和树剖常数小有关?)。

吐槽一点,原题提到了每个点的度数不超过20,但是网上几乎所有OJ上该题的题面都没提到这一点……

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <set>
#include <vector>
#include <queue>
#include <stack>
typedef long long ll;
const int maxn = 100005;
const int maxe = maxn << 1;
int first[maxn];
int next[maxe], to[maxe];
ll dist[maxe];
void add_edge(int u, int v, ll d) {
  static int cnt = 0;
  cnt ++;
  next[cnt] = first[u];
  first[u] = cnt;
  to[cnt] = v;
  dist[cnt] = d;
}
 
int n;
int size[maxn], hson[maxn], fa[maxn], dep[maxn];
ll dis[maxn];
void dfs_1(int x, int father = 0, int depth = 1, ll d = 0) {
  size[x] = 1;
  fa[x] = father;
  dep[x] = depth;
  dis[x] = d;
  int max_siz = 0;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != father) {
      dfs_1(v, x, depth + 1, d + dist[i]);
      size[x] += size[v];
      if(size[v] > max_siz) {
        max_siz = size[v];
        hson[x] = v;
      }
    }
  }
}
int dfn[maxn], top[maxn], tid[maxn];
void dfs_2(int x, int father = 0, int a = 1) {
  static int dfn_clk = 0;
  dfn[x] = ++ dfn_clk;
  tid[dfn[x]] = x;
  top[x] = a;
  if(!hson[x]) {
    return;
  } else {
    dfs_2(hson[x], x, a);
  }
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(v != father && v != hson[x]) {
      dfs_2(v, x, v);
    }
  }
}
int lca(int x, int y) {
  while(top[x] != top[y]) {
    if(dep[top[x]] < dep[top[y]]) std::swap(x, y);
    x = fa[top[x]];
  }
  if(dep[x] > dep[y]) {
    return y;
  } else {
    return x;
  }
}
ll calc_dist(int x, int y) {
  int l = lca(x, y);
  return dis[x] + dis[y] - 2LL * dis[l];
}

bool vis[maxn];
int siz[maxn];
void gen_siz(int x, int f = 0) {
  siz[x] = 1;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != f) {
      gen_siz(v, x);
      siz[x] += siz[v];
    }
  }
}
int nrt, rt;
void gen_rt(int x, int f = 0) {
  bool flag = (siz[x] * 2 >= siz[nrt]);
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != f) {
      flag = (flag && (siz[v] * 2 <= siz[nrt]));
      gen_rt(v, x);
    }
  }
  if(flag) rt = x;
}
ll w[maxn];
int crt, cfa[maxn];
ll pans[maxn], give[maxn], sumv[maxn];
int point2[maxe];
/*
void search_p(int x, std::stack<int> *V, int f = 0) {
  V -> push(x);
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v] && v != f) {
      search_p(v, V, x);
    }
  }
}
*/
int divide(int x) {
  nrt = rt = x;
  gen_siz(x); gen_rt(x);
  x = rt; vis[x] = true;
  for(int i = first[x]; i; i = next[i]) {
    int v = to[i];
    if(!vis[v]) {
      int ch = divide(v);
      point2[i] = ch;
      cfa[ch] = x;
    }
  }
  return x;
}
void update(int x, ll delta) {
  int p = x;
  while(p) {
    pans[p] += delta * calc_dist(p, x);
    if(p != crt) give[p] += delta * calc_dist(x, cfa[p]);
    sumv[p] += delta;
    p = cfa[p];
  }
}
ll get_ans(int x) {
  ll ans = pans[x];
  int p = x;
  while(p != crt) {
    int f = cfa[p];
    ans += pans[f] - give[p];
    ans += calc_dist(x, f) * (sumv[f] - sumv[p]);
    p = cfa[p];
  }
  return ans;
}
ll get_best() {
  int p = crt;
  std::stack<int> S;
  ll now_ans;
  while(true) {
    S.push(p); vis[p] = true;
    bool fix = true;
    now_ans = get_ans(p);
    for(int i = first[p]; i; i = next[i]) {
      int v = to[i];
      if(vis[v]) continue;
      if(get_ans(v) < now_ans) {
        fix = false;
        p = point2[i];
        break;
      }
    }
    if(fix) break;
  }
  while(!S.empty()) {
    int u = S.top(); S.pop();
    vis[u] = false;
  }
  return now_ans;
}

int main() {
  int q; scanf("%d%d", &n, &q);
  for(int i = 0; i < n - 1; i ++) {
    int u, v; ll d; scanf("%d%d%lld", &u, &v, &d);
    add_edge(u, v, d); add_edge(v, u, d);
  }
  dfs_1(1); dfs_2(1);
  crt = divide(1); memset(vis, 0, sizeof(vis));
  while(q --) {
    int u, e; scanf("%d%d", &u, &e);
    update(u, e);
    printf("%lld\n", get_best());
  }
  return 0;
}

[LibreOJ 6238][Baltic2015]Network

LibreOJ真是好用(以后尽可能少用BZOJ)

这题我觉得真是个意识流神题。

考虑所有度数为1的点(姑且称为叶子),这些点是一定要向外连边的(只要有一个度数为1的树边不在一个环中,肯定就出桥了)。

那是否可以只在这种叶子之间连边?答案是肯定的。假设叶子上形成了足够多的环,那么上面的边可以随便上。

那是否叶子配对连边就行了(这说明答案是\(\lceil \frac{l}{2}\rceil\),其中\(l\)是叶子的数目)?答案也是肯定的。但这种方案里显然两个结点间有新边则两点不可能在根的同一棵子树里。

然后就有一种乱搞做法:找到一个根使得每个子树的叶子数都不超过总数的一半(这种点很显然存在),然后从这个根开始DFS,把所有叶子按照DFS序排序一遍,前一半向后一半依次连边。如果叶子数目是奇数,那么最后一个可以随便连。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cctype>
#include <utility>
#include <queue>
#include <set>
#include <vector>
using std::vector;
const int maxn = 500005;
vector<int> G[maxn];

int n;
int leaves[maxn];
vector<int> L;
int leavenum = 0;
void calc_leave(int x, int fa = 0) {
  if(int(G[x].size()) == 1) {
    leaves[x] = 1; L.push_back(x);
    leavenum ++;
  }
  for(auto v : G[x]) {
    if(v != fa) {
      calc_leave(v, x);
      leaves[x] += leaves[v];
    }
  }
}
int gen_rt(int x, int fa = 0) {
  for(auto v : G[x]) {
    if(v != fa && leaves[v] * 2 >= leavenum) {
      return gen_rt(v, x);
    }
  }
  return x;
}
int dfn[maxn];
void calc_dfn(int x, int fa = 0) {
  static int cnt = 0;
  dfn[x] = ++ cnt;
  for(auto v : G[x]) {
    if(v != fa) {
      calc_dfn(v, x);
    }
  }
}

bool cmp(const int &x, const int &y) {
  return dfn[x] < dfn[y];
}
int main() {
  scanf("%d", &n);
  for(int i = 0; i < n - 1; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    G[u].push_back(v); G[v].push_back(u);
  }
  calc_leave(1);
  int rt = gen_rt(1);
  calc_dfn(rt);
  sort(L.begin(), L.end(), cmp);
  printf("%d\n", (leavenum + 1) / 2);
  int half = leavenum / 2;
  for(int i = 0; i < half; i ++) {
    printf("%d %d\n", L[i], L[i + half]);
  }
  if(1 & leavenum) {
    printf("%d %d\n", L[half - 1], L[leavenum - 1]);
  }
  return 0;
}

[BZOJ 3925][ZJOI2015]地震后的幻想乡

赛艇,赛艇.jpg
首先这个问题的本质就是让你求一个边权在\([0, 1]\)间均匀随机分布的无向图的MST的最大边边权的期望……
有一个很经典的式子:
\[E = \int_0^1 p(\geq x)\,\mathrm{d}x\]
然后考虑那个\(p\)咋整。
首先对于每个包含1的点集(我们不妨假设是从点1开始扩展)\(S\),式子可以这么写(这里不妨用\(T\)来表示两个点集间的边的数目):
\[p_{S, x} = \sum_{1\in S_0 \subset S} (1 - x)^{T(S_0, S - S_0)}(1 - p_{S_0, x})\]
显然答案是\(\int_0^1 p_{S, x}\,\mathrm{d}x\),但这玩咋求……
然后我们定义一个状态\(d\):
\[d_{S, k} = \int_0^1 (1 - x)^k p_{S, x}\,\mathrm{d}x\]
把其中的\(p\)展开,整理一下,得到:
\[
\begin{aligned}
d_{S, k}=&\sum_{1\in S_0 \subset S}(\int_0^1(1 - x)^{T(S, S - S_0) + k}\,\mathrm{d}x\\
& - \int_0^1(1 - x)^{T(S, S - S_0) + k}\,p_{S_0,\,x}\,\mathrm{d}x)
\end{aligned}
\]
里面有两大块定积分,前一块还看起来蛮好求的,但后面一块……
不就是\(d_{S_0, T(S, S - S_0) + k}\) 吗?
然后这样整个$d$就可以搞一波状压DP了。
然后观察\(d_{S, 0}\)(这里不妨假设S为全集):
\[d_{S, 0}=\int_0^1(1 - x)^0 p_{S, x}\,\mathrm{d}x = \int_0^1 p_{S, x}\,\mathrm{d}x\]
这不就是我们要的答案吗?
至于边界处理,\(d_{\{1\}, x}\)全部搞成0就行。
代码:
/**************************************************************
    Problem: 3925
    User: danihao123
    Language: C++
    Result: Accepted
    Time:100 ms
    Memory:1272 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <bitset>
typedef double R;
const int maxn = 11;
const int maxm = 50;
int edge[maxm][2];
 
int n, m;
R d[1 << 10][maxm];
bool vis[1 << 10][maxm];
R f(int s, int k) {
  if(s == 1) return 0;
  if(vis[s][k]) return d[s][k];
  d[s][k] = 0;
  int lit_s = s >> 1;
  for(int lit_s0 = (lit_s - 1) & lit_s; ; lit_s0 = (lit_s0 - 1) & lit_s) {
    int s0 = lit_s0 * 2 + 1;
    int t = 0;
    for(int i = 1; i <= m; i ++) {
      int u = edge[i][0], v = edge[i][1];
      if(((1 << u) & s) == 0 || ((1 << v) & s) == 0) continue;
      if((((1 << u) & s0) == 0) ^ (((1 << v) & s0) == 0)) {
        t ++;
      }
    }
    int z = k + t;
    d[s][k] += 1.00 / ((double(z)) + 1.00) - f(s0, z);
    if(s0 == 1) break;
  }
  vis[s][k] = true;
  return d[s][k];
}
 
int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i ++) {
    int u, v; scanf("%d%d", &u, &v); u --, v --;
    edge[i][0] = u, edge[i][1] = v;
  }
  printf("%.6lf\n", f((1 << n) - 1, 0));
  return 0;
}