zhengrui contest 609

这场成绩看上去可以，其实是打的很糟糕的一场比赛。

这场比赛用到的套路：

$1.$动态插入删除线性基以及一类离线后维护删除时间较晚的问题

$2.$对每个质数单独考虑，可能能解决形如$\prod{gcd}$的问题

$3.$对$\sqrt{x}$分类讨论，甚至$\sqrt[3]{x}$。

A

要维护插入和删除的线性基，普通的方法自然是线段树合并。至于$O(nq)$的正解，把套路记住就行了。

方法就是，维护每个数出现时间，尽可能先删除删除时间早的。

还有一个例子就是动态维护图连通性。朴素也是线段树分治和并茶集。那么，倘若维护了边权是删除时间最大生成树，复杂度就能变成$O(nlogn)$。

至于具体怎么实现，看看代码很容易理解。

#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
#define getchar() (*input_pos++)
const int TT = 20 * 2e6;
char input_buffer[TT];
char *input_pos = input_buffer;
inline int getint() {
  int x = 0, p = 1; char c = getchar();	
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
//ruogu_alter
const int N = 2e6 + 5;
int n, q, res, c;
int to[N], val[N], pos[N], id[N];
int b[30], tim[30];
inline int ins(int x, int t) {
  if (!x) return 0;
  for (int i = n - 1; i >= 0; i--) if (x >> i & 1) {
    if (!b[i]) { b[i] = x; tim[i] = t; return 1; }
    else {
      if (tim[i] < t) { swap(tim[i], t); swap(b[i], x); }
      x ^= b[i];
    }
  }
  return 0;
}
inline int del(int t) {
  for (int i = n - 1; i >= 0; i--) if (tim[i] == t) {
    tim[i] = -1; b[i] = 0; 
    return 1;
  }
  return 0;
}
//
int main() {
  fread(input_buffer, 1, TT, stdin);
  n = getint(); q = getint();
  memset(to, -1, sizeof(to));
  memset(tim, -1, sizeof(tim));
  rep(i, q) {
    int op = getint(), x = val[i] = getint();
    if (op == 1) {
      id[c++] = x;
      to[i] = q;
    }
  }
  sort(id, id + c);
  c = unique(id, id + c) - id;
  rep(i, q) {
    if (to[i] >= 0) {
      pos[lower_bound(id, id + c, val[i]) - id] = i;
    }
    else {
      to[pos[lower_bound(id, id + c, val[i]) - id]] = i;
    }
  }
  int sz = 0;
  rep(qq, q) {
    if (to[qq] >= 0) sz += ins(val[qq], to[qq]);
    else sz -= del(qq);
    res ^= (1 << n - sz);
  }
  cout << res << endl;
  return 0;
}

B​

这题可以先写个暴力的$dp$，算出来的其实是贝尔数。。$n=12$的时候，贝尔数是不大的，大概$4*10^6$。这时就可以写一个暴力程序了。。

#include <bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair <int, int>
#define iiii pair <int, pii >
#define mp make_pair
#define INF 1000000000
#define rep(i, x) for(int (i) = 0; (i) < (x); (i)++)
inline int getint() {
  int x = 0, p = 1; char c = getchar();
  while (c <= 32) c = getchar();
  if (c == 45) p = -p, c = getchar();
  while (c > 32) x = x * 10 + c - 48, c = getchar();
  return x * p;
}
using namespace std;
const int mod = 1e9 + 7;
inline void reduce(int &x) { x += x >> 31 & mod; }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
//ruogu_alter
const int N = 20;
const int M = (1 << 15) + 5;
int n, m, e[N], msk[N], mn[M], a[N], res, lim;
//
inline int calc(vector<int> &v) {
  sort(v.begin(), v.end());
  int ans = v.size();
  rep(i, v.size()) ans = mul(ans, v[i] - i + 1);
  return ans;
}
void dfs(int x, int c) {
  if (x == n) {
    vector<int> v;
    rep(i, c + 1) v.emplace_back(mn[msk[i]]);
    reduce(res += calc(v) - mod);
    return;
  }
  rep(i, c + 2) if (!(msk[i] & e[x])) {
    msk[i] |= (1 << x);
    dfs(x + 1, max(c, i));
    msk[i] ^= (1 << x);
  }
}
void dfs2(int x) {
  if (x == n) {
    rep(i, lim + 1) reduce(res += (msk[i] > 0) - mod);
    return;
  }
  rep(i, a[x] + 1) if (!(msk[i] & e[x])) {
    msk[i] |= (1 << x);
    dfs2(x + 1);
    msk[i] ^= (1 << x);
  }
}
int main() {
  n = getint(); m = getint();
  rep(i, n) {
    a[i] = getint();
    lim = max(lim, a[i]);
  }
  rep(mask, 1 << n) {
    mn[mask] = INF;
    rep(i, n) if (mask >> i & 1) mn[mask] = min(mn[mask], a[i]);
  }
  rep(i, m) {
    int x = getint() - 1, y = getint() - 1;
    e[x] |= (1 << y); e[y] |= (1 << x);
  }
  if (lim <= 2) {
    dfs2(0);
    cout << res << endl;
    return 0;
  }
  if (m == n * (n - 1) / 2) {
    vector<int> v;
    rep(i, n) v.emplace_back(a[i]);
    printf("%d\n", calc(v));
    return 0;
  }
  dfs(0, -1);
  cout << res << endl;
  return 0;
}

这个有$79$，分数其实非常实惠，如果正式考试的话应该这样写是不错的选择。但是其实再多想几分钟，就能直接发现正解，就是$O(n3^n)$的$dp[S][x]$表示已经集合$S$已经选了$x$个相等的方案数。为了方便统计，我们要尽可能把当前未在集合里$a$最小的划进来。

http://zhengruioi.com/submission/228619

留个坑，看看桌面上的论文。。

留个坑，看看子集卷积。。http://zhengruioi.com/submission/227500

C

对于这一类$gcd$的问题那么自然要看看

$1.$容斥

$2.$形如对区间的$dp$

$3.$对每个质数单独考虑

就这题而言，那当然需要的诀窍正是：对每个质数单独考虑！！！

现在我们考虑插入一个数$x$，他对现有集合的贡献是

若$p^k|x$，贡献就是$p^{2^{ cnt[p^k]-1}}$。

然后对每个$p^k|x$，$cnt[p^k] +1$。

自然要莫队。先是$O(n\sqrt{q}logwlogw)$，大抵因为既要分解质因数，又要快速米；然后想办法把快速幂去掉；然后就是精彩的套路。

一个数大于$\sqrt{w}$的质因数只有一个！这个可以直接$O(1)$插入。

至于所有$p \leq \sqrt{w}$，$p^k<w$，这样的所有$p$的$\sum{k}$只有$O(\frac{\sqrt{w}}{logw})$！！震撼全场！

也就是说对于所有$p \leq \sqrt{w}$，我们都可以不用莫队而是直接在静态数组上用前缀和$O(\frac{\sqrt{w}}{logw})$求答案！

总复杂度$n\sqrt{q}$。