Review

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

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

Solution

T1 hike

nn 个点， qq 个询问

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
//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

nn 种物品，两个属性：体积 vv，价值 ww 。

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

1≤vi≤c1\le v_i\le c，c=300c=300

n,k≤105n,k\le 10^5

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

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

下面证明决策单调性。

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

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

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

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

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

则有转移方程

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

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

设 j1<j2j_1< j_2，它们的决策点分别为 k1,k2k_1,k_2。

不妨假设 k2<k1k_2< k_1 ，即 k2<k1≤j1<j2k_2<k_1\leq j_1<j_2。

由于 k2k_2 是 j2j_2 的最优决策点，所以 f(i−1,k1)+w(j2−k1)≤f(i−1,k2)+w(j2−k2)f(i-1,k_1)+w(j_2-k_1)\leq f(i-1,k_2)+w(j_2-k_2)

因为 ww 的斜率不增，所以 w(j2−k1)−w(j1−k1)j2−k1−j1+k1≥w(j2−k2)−w(j1−k2)j2−k2−j1+k2\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(j1−k1)−w(j2−k1)≤w(j1−k2)−w(j2−k2)w(j_1-k_1)-w(j_2-k_1)\leq w(j_1-k_2)-w(j_2-k_2)。

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

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

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

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

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

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

解得 T(n)=O(nlog⁡n)T(n)=O(n\log n)

总共需要求解 cc 次，故总复杂度 O(cklog⁡k)O(ck\log k)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//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矩阵 CC 求矩阵 A,BA,B 的个数 cntCcnt_C，使得满足 c_{i,j}=\left(\sum_\limits{k=1}^{n}a_{i,k}b_{k,j}\right)\bmod2

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

将 AA、 CC 看成由 nn 个列向量构成的矩阵，则 CjC_j 可以由 若干个 AiA_i 异或得到，而这“若干”由 BB 的第 jj 列决定。

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

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

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

设 fi,jf_{i,j} 表示前 n×in\times i 的矩阵中，秩为 jj 的方案数。

则有转移方程：

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

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

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

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

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

所以最终的答案是 1fn,rank⁡C∑i=rank⁡Cnfn,i⋅fi,rank⁡C⋅2n(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(n2+n3ω)O(n^2+\frac{n^3}{\omega})

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
//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;
}