Review

考试时一直在肝论文，发现 2017 国集论文里面有决策单调性优化 dp 的内容，终于在考试最后 2 分钟调过样例。

结果因为没有滚数组导致 MLE，沦为暴力 20pts。

Solution

T1 hike

$n$ 个点， $q$ 个询问

两种询问，分别是合并两树和查询树中里给定点最远的点的距离

LCT 维护树的直径板子题 $O(n\log n)$ ，可惜我不会，只好启发式合并暴力处理倍增数组。

考虑两颗树的直径端点 $a,b,c,d$ ，则合并出的新树直径只有可能是这 4 个数中的 2 个，合并时判断即可， $O(n\log^2n)$ 。

//author: ycp | https://ycpedef.github.io
//#pragma GCC diagnostic error "-std=c++11"
//#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdarg>
#include <vector>
//#define DEBUG
#ifdef DEBUG
#   define debug(x) cerr << #x << " = " << x << endl
#   define debugf(...) fprintf(stderr, __VA_ARGS__)
#   define debugs(x) fputs(x"\n", stderr)
#else
#   define debug(x) 1
#   define debugf(...) 1
#   define debugs(x) 1
#endif
using namespace std;
template <class T> bool cmax(T &a, T b) { return b > a ? (a = b, 1) : 0; }
template <class T> bool cmin(T &a, T b) { return b < a ? (a = b, 1) : 0; }
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int f = 0;
    while (!isdigit(c)) { f ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= f ? -1 : 1;
}
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

const int MAXN = 3e6 + 10;
const int LOGN = 30;

struct Edge {
    int to;
    int next;
} e[MAXN];

int n, q, logn;
int fa[MAXN][LOGN];
int dep[MAXN];
int diam[MAXN];
int s[MAXN], t[MAXN];
int root[MAXN], head[MAXN], tot;
vector <int> subtree[MAXN];

void addEdge(int x, int y) {
    tot++;
    e[tot].to = y;
    e[tot].next = head[x];
    head[x] = tot;
}

void dfs(int u) {
    for (int i = 1; i <= logn; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    //debugf("fa[%d][%d] = %d, dep[%d] = %d\n", u, 0, fa[u][0], u, dep[u]);
    for (int i = head[u], v; i; i = e[i].next) {
        v = e[i].to;
        if (v == fa[u][0]) continue;
        dep[v] = dep[u] + 1;
        fa[v][0] = u;
        dfs(v);
    }
}

int lca(int a, int b) {
    int _a = a, _b = b;
    if (dep[a] < dep[b]) swap(a, b);
    int c = dep[a] - dep[b];
    for (int i = 0; i <= logn; i++) {
        if (c & (1 << i)) {
            a = fa[a][i];
        }
    }
    if (a == b) return a;
    for (int i = logn; i >= 0; i--) {
        if (fa[a][i] != fa[b][i]) {
            a = fa[a][i], b = fa[b][i];
        }
    }
    return fa[a][0];
}

int dist(int a, int b) {
    int c = lca(a, b);
    //debugf("dist(%d, %d) = %d\n", a, b, dep[a] + dep[b] - dep[c] * 2);
    return dep[a] + dep[b] - dep[c] * 2;
}

void print_siz() {
#ifdef DEBUG
    for (int i = 1; i <= n; i++) {
        if (root[i] == i) {
            //debugf("subtree[%d].size = %ld\n", i, subtree[i].size());
            //debugf("point = %d / %d  len = %d\n", s[i], t[i], diam[i]);
        }
    }
#endif
}

void merge(int x, int y) {
    //debugs("-----------------");
    //debugf("merge (%d, %d) \n", x, y);
    int rtx = root[x], rty = root[y];
    if (subtree[rtx].size() > subtree[rty].size()) {
        swap(rtx, rty);
        swap(x, y);
    }
    dep[x] = dep[y] + 1;
    fa[x][0] = y;
    dfs(x);
    addEdge(x, y);
    addEdge(y, x);
    for (int x = 0, len = subtree[rtx].size(), u; x < len; x++) {
        u = subtree[rtx][x];
        root[u] = rty;
        subtree[rty].push_back(u);
    }
    subtree[rtx].clear();
    int a = s[rtx], b = t[rtx], c = s[rty], d = t[rty];
    //debug(a), //debug(b), //debug(c), //debug(d);
    if (cmax(diam[rty], dist(a, b))) { s[rty] = a, t[rty] = b; }
    if (cmax(diam[rty], dist(a, c))) { s[rty] = a, t[rty] = c; }
    if (cmax(diam[rty], dist(a, d))) { s[rty] = a, t[rty] = d; }
    if (cmax(diam[rty], dist(b, c))) { s[rty] = b, t[rty] = c; }
    if (cmax(diam[rty], dist(b, d))) { s[rty] = b, t[rty] = d; }
    if (cmax(diam[rty], dist(c, d))) { s[rty] = c, t[rty] = d; }
}

int query(int u) {
    //debugs("-----------------");
    //debugf("query (%d) \n", u);
    int rtu = root[u];
    return max(dist(u, s[rtu]), dist(u, t[rtu]));
}

int main() {
    int general_type, lastans = 0;
    fastin >> general_type;
    fastin >> n >> q;
    while ((1 << logn) < n) {
        logn++;
    }
    //debug(logn);
    for (int i = 1; i <= n; i++) {
        root[i] = i;
        s[i] = i;
        t[i] = i;
        diam[i] = 0;
        subtree[i].push_back(i);
    }
    for (int i = 1, type, u, v; i <= q; i++) {
        fastin >> type;
        if (type == 1) {
            fastin >> u >> v;
            if (general_type) {
                u ^= lastans;
                v ^= lastans;
            }
            merge(u, v);
            print_siz();
        } else {
            fastin >> u;
            if (general_type) {
                u ^= lastans;
            }
            printf("%d\n", lastans = query(u));
        }
    }
    return 0;
}

T2 jewelry

$n$ 种物品，两个属性：体积 $v$ ，价值 $w$ 。

询问体积为 $1\to k$ 的背包分别能装下多少价值的物品。

$1\le v_i\le c$ ， $c=300$

$n,k\le 10^5$

决策单调性优化 dp，分治处理决策点，复杂度 $O(ck\log k)$ 。

参见《浅谈决策单调性动态规划的线性解法》。

下面证明决策单调性。

显然对于价格相同的一类物品，从价值高的取到价值低的比反过来更优，所以先排个序。

设 $f(i,j)$ 表示取第 $1$ 到 $i$ 类物品，体积不超过 $j$ 的最大价值。

考虑 $f(i,j)$ 怎么求。

对于特定的 $i$ ，我们把模 $i$ 同余（设余数为 $d$ ）的一类体积拿出来，重新标号，显然总共有 $\dfrac{n}{i}$ 个体积。

重新标号的意思是，对于以下的 $f(i,j)$ ，它表示的实际体积为 $ij+d$ 。

则有转移方程

f(i,j)=\max\limits_{k=0}^{j}f(i-1,k)+w(j-k)

这里的 $w(j-k)$ 表示的是体积为 $i$ 的物品中取前 $j-k$ 个的最大价值，若 $j-k$ 超过体积为 $i$ 的物品个数，则 $w(j-k)$ 是体积为 $i$ 的物品的所有价值和，易得 $w$ 是下凸的函数。

设 $j_1< j_2$ ，它们的决策点分别为 $k_1,k_2$ 。

不妨假设 $k_2< k_1$ ，即 $k_2<k_1\leq j_1<j_2$ 。

由于 $k_2$ 是 $j_2$ 的最优决策点，所以 $f(i-1,k_1)+w(j_2-k_1)\leq f(i-1,k_2)+w(j_2-k_2)$

因为 $w$ 的斜率不增，所以 $\dfrac{w(j_2-k_1)-w(j_1-k_1)}{j_2-k_1-j_1+k_1}\geq \dfrac{w(j_2-k_2)-w(j_1-k_2)}{j_2-k_2-j_1+k_2}$ ，即 $w(j_1-k_1)-w(j_2-k_1)\leq w(j_1-k_2)-w(j_2-k_2)$ 。

将两个不等式加起来，得到 $f(i-1,k_1)+w(j_1-k_1)\leq f(i-1,k_2)+w(j_1-k_2)$ ，与 $k_1$ 是 $j_1$ 最优决策点矛盾。

所以 $\forall j_x<j_y,\ k_x\leq k_y$ 。而这个题的决策有个特点，即不依赖于同一层的 dp 值，所以可以分治处理。

传入四个参数 $l,r,k_l,k_r$ 表示正在处理第 $l$ 到第 $r$ 个 dp 值，决策点范围为 $[k_l,k_r]$ 。

设 $m=\dfrac{(l+r)}{2}$ ，则直接 $O(r-l)$ 求出 $f[m]$ 以及其决策点 $pos$ ，即可递归求解 $(l,m-1,k_l,pos)$ 和 $(m+1,r,pos,k_r)$ 。

设递归复杂度为 $T(n)$ ( $n$ 是编号区间长度)

则有 $T(n)=2T(n/2)+n$ 。

解得 $T(n)=O(n\log n)$

总共需要求解 $c$ 次，故总复杂度 $O(ck\log k)$

//author: ycp | https://ycpedef.github.io
//#pragma GCC diagnostic error "-std=c++11"
//#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdarg>
#include <vector>
#define debug(x) cerr << #x << " = " << x << endl
#define debugf(...) fprintf(stderr, __VA_ARGS__)
#define debugs(x) fputs(x"\n", stderr)
using namespace std;
template <class T> bool cmax(T &a, T b) { return b > a ? (a = b, 1) : 0; }
template <class T> bool cmin(T &a, T b) { return b < a ? (a = b, 1) : 0; }
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int f = 0;
    while (!isdigit(c)) { f ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= f ? -1 : 1;
}
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

#define int long long

const int MAXN = 50010;
const int MAXC = 610;
const int inf = 0x3f3f3f3f3f3f3f;

int n, k, maxc;
int f[MAXC][MAXN];
int pre[MAXC];
vector<int> val[MAXC];
int w[MAXC][MAXN];

int cur, res;
void dp(int l, int r, int k_l, int k_r) {
    //debugf("--- dp(%lld, %lld, %lld, %lld) ---\n", l, r, k_l, k_r);
    int mid = (r + l) / 2;
    int pos = k_l;
    for (int i = k_l; i <= min(k_r, mid); i++) {
        if (f[pre[cur]][i * cur + res] + w[cur][mid - i] > f[pre[cur]][pos * cur + res] + w[cur][mid - pos]) {
            pos = i;
        }
    }
    f[cur][mid * cur + res] = f[pre[cur]][pos * cur + res] + w[cur][mid - pos];
    //debugf("mid = %lld, pos = %lld\n", mid, pos);
    //debugf("f[%lld][%lld] = %lld\n", pre[cur], pos * cur + res, f[pre[cur]][pos * cur + res]);
    //debugf("w[%lld][%lld] = %lld\n", cur, mid - pos, w[cur][mid - pos]);
    //debugf("set f[%lld][%lld] = %lld\n", cur, mid * cur + res, f[pre[cur]][pos * cur + res] + w[cur][mid - pos]);
    if (l <= mid - 1)
        dp(l, mid - 1, k_l, pos);
    if (mid + 1 <= r)
        dp(mid + 1, r, pos, k_r);
}

signed main() {
//    freopen("jewelry.in", "r", stdin);
//    freopen("jewelry.out", "w", stdout);
    fastin >> n >> k;
    for (int i = 1, v, c; i <= n; i++) {
        fastin >> c >> v;
        val[c].push_back(v);
        cmax(maxc, c);
    }
    for (int i = 1, p = 0; i <= maxc; i++) {
        if (val[i].size() == 0) {
            continue;
        }
        pre[i] = p;
        sort(val[i].begin(), val[i].end(), greater<int>());
        w[i][0] = 0;
        for (int j = 1, siz = val[i].size(); j <= siz; j++) {
            w[i][j] = w[i][j - 1] + val[i][j - 1]; // push w[j]
        }
        for (int j = val[i].size() + 1; j <= k * 2; j++) {
            w[i][j] = w[i][j - 1];
        }
        p = i;
    }
    for (int i = 1; i <= maxc; i++) {
        for (int j = 0; j <= k * 2; j++) {
            f[i][j] = -inf;
        }
    }
    f[0][0] = 0;
    for (int i = 1; i <= maxc; i++) {
        if (val[i].size() == 0) continue;
        for (int j = 0; j < i; j++) {
            cur = i, res = j;
            //debugf("\n------cur=%lld, res=%lld------\n", cur, res);
            dp(0, k / i + 1, 0, k / i + 1);
        }
    }
    for (int i = 1; i <= k; i++) {
        printf("%lld ", f[maxc][i]);
    }
    return 0;
}

T3 mat

给定01矩阵 $C$ 求矩阵 $A,B$ 的个数 $cnt_C$ ，使得满足 $c_{i,j}=\left(\sum_\limits{k=1}^{n}a_{i,k}b_{k,j}\right)\bmod2$

01 矩阵元素的加法就是异或。

将 $A$ 、 $C$ 看成由 $n$ 个列向量构成的矩阵，则 $C_j$ 可以由若干个 $A_i$ 异或得到，而这“若干”由 $B$ 的第 $j$ 列决定。

有结论：对于秩一定的矩阵 $C$ ，其答案都相等。

对 $C$ 做初等行变换不会改变 $C$ 的秩的大小，将 $C$ 变为 $C'$ ，可以对 $A$ 做一样的变换为 $A'$ ， $(A',C')$ 仍然是一组答案，所以对于任意秩一定的矩阵 $C$ 答案都是一样的。

所以可以考虑把所有秩为 $\operatorname{rank} C$ 的矩阵答案加起来，除以所有秩为 $\operatorname{rank} C$ 的矩阵个数即可。

设 $f_{i,j}$ 表示前 $n\times i$ 的矩阵中，秩为 $j$ 的方案数。

则有转移方程：

f_{i,j}=f_{i-1,j}\cdot2^{j}+f_{i-1,j-1}\cdot(2^n-2^j)

即分两种情况，判断新的向量是否使得秩增大。

此时要求的答案是 $\sum\limits_{\operatorname{rank}M=\operatorname{rank}C}cnt_M$ 。

对于一个秩为 $\operatorname{rank} A=i(i\ge \operatorname{rank}C)$ 的矩阵，它可以张成 $f_{i,\operatorname{rank}C}$ 个 $C$ 矩阵，而 $B$ 矩阵的个数是 $2^{n(n-i)}$ 个，所以它对答案的贡献是 $f_{i,\operatorname{rank} C}\cdot2^{n(n-i)}$ 。

$B$ 矩阵的个数是 $2^{n(n-i)}$ 个，证明：对于 $B$ 的每一行，前 $i$ 个元素都已经确定了，而后面 $n-i$ 个元素是自由元，随便取 $0$ 或者 $1$ 都可以，故有 $2^{n-i}$ 种方案，而 $B$ 有 $n$ 行，共 ${2^{n-i}}^n=2^{n(n-i)}$ 。

所以最终的答案是 $\cfrac{1}{f_{n,\operatorname{rank} C}}\sum\limits_{i=\operatorname{rank}C}^{n}f_{n,i}\cdot f_{i,\operatorname{rank}C}\cdot 2^{n(n-i)}$

bitset 高消

复杂度 $O(n^2+\frac{n^3}{\omega})$

//author: ycp | https://ycpedef.github.io
//#pragma GCC diagnostic error "-std=c++11"
//#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdarg>
#include <bitset>
#define debug(x) cerr << #x << " = " << x << endl
#define debugf(...) fprintf(stderr, __VA_ARGS__)
#define debugs(x) fputs(x"\n", stderr)
using namespace std;
template <class T> bool cmax(T &a, T b) { return b > a ? (a = b, 1) : 0; }
template <class T> bool cmin(T &a, T b) { return b < a ? (a = b, 1) : 0; }
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int f = 0;
    while (!isdigit(c)) { f ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= f ? -1 : 1;
}
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

#define int long long

const int MAXN = 2010;
const int mod = 1e9 + 7;

int n;
bitset <MAXN> a[MAXN];
int rk;
int dp[MAXN][MAXN];

int getrank() {
    int res = 0;
    for (int i = 1, j = 1; j <= n; i++, j++) {
        bool ok = 0;
        for (int k = i; k <= n; k++) {
            if (a[k][j]) {
                ok = 1;
                swap(a[k], a[i]);
                break;
            }
        }
        if (!ok) {
            i--;
            continue;
        }
        res++;
        for (int k = i + 1; k <= n; k++) {
            if (a[k][j]) {
                a[k] ^= a[i];
            }
        }
    }
    return res;
}

int power(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) {
            (res *= a) %= mod;
        }
        (a *= a) %= mod;
        b >>= 1;
    }
    return res;
}

int inv(int x) {
    return power(x, mod - 2);
}

signed main() {
    fastin >> n;
    for (int i = 1, v; i <= n ;i++) {
        for (int j = 1; j <= n; j++) {
            fastin >> v;
            a[i][j] = v;
        }
    }
    rk = getrank();
    //debug(rk);
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = dp[i - 1][0];
        for (int j = 1; j <= i ;j++) {
            dp[i][j] = (power(2, j) * dp[i - 1][j] % mod + (power(2, n) - power(2, j - 1) + mod) % mod * dp[i - 1][j - 1] % mod) % mod;
            //debugf("dp[%lld][%lld] = %lld\n", i, j, dp[i][j]);
        }
    }
    int ans = 0;
    for (int i = rk; i <= n; i++) {
        ans = (ans + dp[n][i] * dp[i][rk] % mod * power(2, n * (n - i)) % mod) % mod;
    }
    ans = ans * inv(dp[n][rk]) % mod;
    cout << ans << endl;
    return 0;
}

Cauphenuny's blog

20210220 考试总结

Review

Solution

T1 hike

T2 jewelry

T3 mat