THUSC2016/2017泛做

THUSC2016/2017

补退选

可持久化\(\text{Trie}\)搞一搞,每个节点记录一下前缀出现的最大次数,然后二分答案就好了。复杂度\(O(n|S|\log n)​\)。好像有更高妙的做法可以不二分,但是由于我很菜并不会。

代码:

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
/*
* 2291.cpp
* This file is part of 2291
*
* Copyright (C) 2019 - ViXbob
*
* 2291 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 2291 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 2291. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int n, root[maxn], tot, lstans, a[maxn], b[maxn], c[maxn], len;
char s[65];

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}

struct Node {
int ch[10], sum, mx;
} t[maxn * 65];

inline void insert(int u, int pre) {
static char s[65];
scanf("%s", s + 1);
for(int i = 1; s[i]; i++) {
t[u] = t[pre]; t[u].sum++;
if(t[u].sum > t[u].mx) t[u].mx = t[u].sum;
t[u].ch[s[i] - 'a'] = ++tot;
u = t[u].ch[s[i] - 'a'];
pre = t[pre].ch[s[i] - 'a'];
}
t[u] = t[pre]; t[u].sum++;
if(t[u].sum > t[u].mx) t[u].mx = t[u].sum;
}

inline void del(int u, int pre) {
static char s[65];
scanf("%s", s + 1);
for(int i = 1; s[i]; i++) {
t[u] = t[pre]; t[u].sum--;
t[u].ch[s[i] - 'a'] = ++tot;
u = t[u].ch[s[i] - 'a'];
pre = t[pre].ch[s[i] - 'a'];
}
t[u] = t[pre]; t[u].sum--;
}

inline int query(int u) {
rep(i, 1, len) u = t[u].ch[s[i] - 'a'];
return t[u].mx;
}

inline int calc(int l, int r, int lim) {
int mid = (l + r) / 2, rnt = -1;
while(l <= r) {
mid = l + r >> 1;
if(query(root[mid]) > lim) rnt = mid, r = mid - 1;
else l = mid + 1;
} return rnt;
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read();
rep(i, 1, n) {
int opt = read(), A, B, C, D;
root[i] = ++tot;
t[root[i]] = t[root[i - 1]];
if(opt == 1) insert(root[i], root[i - 1]);
else if(opt == 2) del(root[i], root[i - 1]);
else {
scanf("%s%d%d%d", s + 1, &A, &B, &C);
len = strlen(s + 1);
D = (1ll * A * abs(lstans) + B) % C;
// cerr << D << endl;
printf("%d\n", lstans = calc(1, i, D));
}
}
return 0;
}

成绩单

妙妙\(\text{dp}\)。因为一段区间的消除只和这个区间的最大最小值有关所以设计状态\(f[i][j][l][r]\)表示\([i,j]\)这个区间内只剩在\([l,r]\)之间的数的最小花费,\(g[i][j]\)表示把\([i, j]\)这个区间消除的最小花费。

对于\(g[i][j]\)我们显然有转移: \[ \begin{aligned}f[i][k][l][r]+g[k+1][j] \to g[i][j],i \le k <r\end{aligned} \] 对于\(f[i][j][l][r]\)我们可以枚举一个点来更新最大最小值有转移: \[ \begin{aligned}f[i][j][l][r] + g[j+1][k-1]\to f[i][k][\min(w[k],l)][\max(w[k],r)],j<k\le n\\f[i][j][l][r]+g[k+1][i-1]\to f[k][j][\min(w[k],l)][\max(w[k],r)],1\le k<i\end{aligned} \] 复杂度\(O(n^5)\),但是上界很松所以跑得飞快。

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
/*
* 2292.cpp
* This file is part of 2292
*
* Copyright (C) 2019 - ViXbob
*
* 2292 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 2292 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 2292. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 50 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int n, w[maxn], f[maxn][maxn][maxn][maxn], g[maxn][maxn], pos[maxn], tot, a, b;

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); a = read(); b = read();
rep(i, 1, n) pos[++tot] = w[i] = read();
sort(pos + 1, pos + 1 + tot);
tot = unique(pos + 1, pos + 1 + tot) - pos - 1;
rep(i, 1, n) w[i] = lower_bound(pos + 1, pos + 1 + tot, w[i]) - pos;
memset(f, 0x3f, sizeof(f));
rep(l, 1, n) rep(r, l, n) g[l][r] = inf;
rep(i, 1, n) f[i][i][w[i]][w[i]] = 0, g[i][i] = a;
rep(len, 2, n) for(int l = 1, r = l + len - 1; r <= n; l++, r++) {
rep(h, l, r - 1) rep(i, 1, tot) rep(j, i, tot) if(f[l][h][i][j] != inf)
f[l][r][min(i, w[r])][max(j, w[r])] = min(f[l][r][min(i, w[r])][max(j, w[r])], f[l][h][i][j] + g[h + 1][r - 1]);
rep(h, l + 1, r) rep(i, 1, tot) rep(j, i, tot) if(f[l][h][i][j] != inf)
f[l][r][min(i, w[l])][max(j, w[l])] = min(f[l][r][min(i, w[l])][max(j, w[l])], f[h][r][i][j] + g[l + 1][h - 1]);
rep(h, l, r) rep(i, 1, tot) rep(j, i, tot) if(f[l][h][i][j] != inf)
g[l][r] = min(g[l][r], f[l][h][i][j] + a + b * (pos[j] - pos[i]) * (pos[j] - pos[i]) + g[h + 1][r]);
}
cout << g[1][n] << endl;
return 0;
}
/*
10
3 1
4 + 3 + 4 + 4
7 6 7 7 1 2

*/

巧克力

先考虑一下没有第二问怎么做:

对于选择至少\(k\)种颜色,我们可以随机的把每种颜色映射到\(k\)个集合中去,并且保证这\(k\)中颜色两两不在同一个集合的概率为\(\frac{k!}{k^k}\),然后直接斯坦纳树就好了。当\(k=5\)时我们理论上跑\(26\)次就可以做到\(99\%\)的正确率,然后因为时限比较松我们做\(100\sim 200\)次都是没问题的。

考虑第二问:

实际上对于一个固定的颜色映射第一问的答案都是固定的,所以我们二分答案以后将\(a\)值大于二分值的设为\(1\),小于等于的设为\(-1\),用这个权值跑斯坦纳树,最后判断是否小于零来\(\text{check}\)就好了。

复杂度\(O(\omega nm3^k\log {nm})\)。(\(\omega\)为随机的次数)

但问题就是不管我随机多少次我最高都只有\(97\)分。暴风哭泣.jpg

代码:

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
/*
* 2977.cpp
* This file is part of 2977
*
* Copyright (C) 2019 - ViXbob
*
* 2977 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 2977 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 2977. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 255;
const int P = 998244353;
const int inf = 0x3f3f3f3f;
const int fx[4] = {0, 1, 0, -1};
const int fy[4] = {1, 0, -1, 0};

std::mt19937 Rand(19260817);

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int n, m, k, T, a[maxn][maxn], c[maxn][maxn], pos[maxn * maxn], id[maxn * maxn], tot, U;
int Case, ans = inf, ra[maxn][maxn], col[maxn][maxn], vis[maxn][maxn], mnblocks, mnval;
int posa[maxn], tota;
pair<int, int> f[maxn][maxn][1 << 5], w[maxn][maxn];

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}

pair<int, int> operator + (const pair<int, int> &a, const pair<int, int> &b) {
return mp(a.first + b.first, a.second + b.second);
}

pair<int, int> operator - (const pair<int, int> &a, const pair<int, int> &b) {
return mp(a.first - b.first, a.second - b.second);
}

queue<pair<int, int> > q;

inline pair<int, int> check(int mid, pair<int, int> rnt = mp(inf, inf)) {
rep(i, 1, n) rep(j, 1, m) w[i][j] = mp(1, a[i][j] <= mid ? -1 : 1);
rep(i, 0, n) rep(j, 0, m) rep(S, 0, U) f[i][j][S] = mp(inf, inf);
rep(i, 1, n) rep(j, 1, m) if(col[i][j] != -1) f[i][j][1 << col[i][j]] = w[i][j];
rep(S, 0, U) {
rep(x, 1, n) rep(y, 1, m) if(col[x][y] != -1) {
for(int T = S; T; T = (T - 1) & S)
f[x][y][S] = min(f[x][y][S], f[x][y][T] + f[x][y][S ^ T] - w[x][y]);
q.push(mp(x, y)); vis[x][y] = 1;
}
while(q.size()) {
int x = q.front().first, y = q.front().second; q.pop();
vis[x][y] = 0;
rep(i, 0, 3) {
int dx = x + fx[i], dy = y + fy[i];
if(dx < 1 || dx > n || dy < 1 || dy > m || col[dx][dy] == -1) continue;
if(f[x][y][S] + w[dx][dy] < f[dx][dy][S]) {
f[dx][dy][S] = f[x][y][S] + w[dx][dy];
if(!vis[dx][dy]) q.push(mp(dx, dy)), vis[dx][dy] = 1;
}
}
}
}
rep(x, 1, n) rep(y, 1, m) rnt = min(rnt, f[x][y][U]);
return rnt;
}

inline void Solve() {
// random_shuffle(pos + 1, pos + 1 + tot);
rep(i, 1, tot) id[pos[i]] = Rand() % k;
rep(i, 1, n) rep(j, 1, m) col[i][j] = c[i][j] > 0 ? id[c[i][j]] : -1;
int l = 1, r = tota, mid, Ans0 = inf, Ans1 = inf;
while(l <= r) {
mid = l + r >> 1;
pair<int, int> tmp = check(posa[mid]);
if(tmp.first > mnblocks || tmp.first == inf) break;
Ans0 = tmp.first;
if(tmp.second <= 0) Ans1 = min(Ans1, posa[mid]), r = mid - 1;
else l = mid + 1;
}
if(Ans0 < mnblocks) mnblocks = Ans0, mnval = Ans1;
else if(Ans0 == mnblocks) mnval = min(mnval, Ans1);
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
T = read();
while(T--) {
n = read(); m = read(); k = read(); tot = 0; mnblocks = mnval = inf;
rep(i, 1, n) rep(j, 1, m) { c[i][j] = read(); if(c[i][j] != -1) pos[++tot] = c[i][j]; }
rep(i, 1, n) rep(j, 1, m) posa[++tota] = a[i][j] = read();
U = (1 << k) - 1;
sort(pos + 1, pos + 1 + tot);
tot = unique(pos + 1, pos + 1 + tot) - pos - 1;
sort(posa + 1, posa + 1 + tota);
tota = unique(posa + 1, posa + 1 + tota) - posa - 1;
if(tot < k) { puts("-1 -1"); continue; }
Case = 233;
while(Case--) Solve();
printf("%d %d\n", mnblocks, mnval);
}
return 0;
}

杜老师

就是要求你选出来的数对于每一个质因子的次幂和都是偶数,如果我们把每个数看成一个二进制,二进制的每一位都表示对于某个质因子的次幂的奇偶性。然后相当于要选出来若干个二进制使得异或之后等于\(0\)

然后我们有个暴力的做法,直接把区间\([l,r]\)的每个数对应的二进制插入线性基后答案就是\(2^{r-l+1-线性基的大小}\)。复杂度\(O(n\frac{\pi^2(n)}{\omega})\)。(\(\pi(n)\)表示素数个数)可以获得\(50pts\)

但考虑到如果一个素数大于\(\sqrt{r}\)那么他是一定会被插入到线性基里去的,所以实际上我们只用考虑\(\sqrt{r}\)内的素数就好了。复杂度\(O(n\frac{\pi^2(\sqrt{n})}{\omega})\)。根据常数优秀程度可以获得\(70\sim 80pts\)。具体的:

我们对于每个数按照它的最大素因子排序对于同一段连续的区间且这个区间的最大素因子都大于\(\sqrt{r}\)的数我们钦定第一个数会被插入到线性基内,然后把其它的数的二进制都异或上它的再插入线性基就好了。(相当于模拟插入线性基的过程)

最后有个结论当区间长度大于等于\(2 \times \sqrt{r-l+1}\)时我们可以认为线性基一定会被插满,所以最后答案就是\(2^{r-l+1-区间素数个数}\)。然后加上这个特判后跑得就飞快了。

注意到这里预处理每个数的素因子要\(O(n)\)筛出每个数的最大/小素因子后,就可以做到严格\(O(\log n)\)分解了。

代码:

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
/*
* 2978.cpp
* This file is part of 2978
*
* Copyright (C) 2019 - ViXbob
*
* 2978 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 2978 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 2978. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e7 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;
const int maxm = maxn << 2;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int T, l[(int)(1e2 + 5)], r[(int)(1e2 + 5)], k, n, len, size;
int prime[maxn], mxpri[maxn], cnt, sucins, big, pos[maxn];
bool vis[maxn];
pair<int, int> a[maxn];

typedef bitset<450> BIT;
BIT B[450], now, pre;

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}

inline void PreSolve() {
vis[1] = 1;
rep(i, 2, n) {
if(!vis[i]) prime[++cnt] = i, mxpri[i] = i, pos[i] = cnt - 1;
for(int j = 1; j <= cnt && prime[j] * i <= n; j++) {
mxpri[prime[j] * i] = mxpri[i];
vis[prime[j] * i] = 1;
if(i % prime[j] == 0) break;
}
}
}

inline bool insert(BIT &x) {
if(sucins >= size) return false;
dep(i, size - 1, 0) if(x[i]) {
if(B[i][i]) x ^= B[i];
else return B[i] = x, true;
} return false;
}

inline void Get_fac(int x, BIT &now) {
now.reset();
if(mxpri[x] > k) x /= mxpri[x];
while(x != 1) {
int t = mxpri[x], con = 0;
while(x % t == 0) x /= t, con++;
now[pos[t]] = con & 1;
}
}

inline void Solve1(int l, int r) {
k = sqrt(r); sucins = big = 0;
size = upper_bound(prime + 1, prime + 1 + cnt, k) - prime - 1;
rep(i, 0, size - 1) B[i].reset();
len = r - l + 1;
rep(i, l, r) a[i - l + 1] = mp(mxpri[i], i);
sort(a + 1, a + 1 + len);
rep(i, 1, len) {
int t = sqrt(a[i].second);
if(t * t == a[i].second) continue;
Get_fac(a[i].second, now);
if(a[i].first <= k) sucins += insert(now);
else if(a[i].first != a[i - 1].first) big++, pre = now;
else now ^= pre, sucins += insert(now);
}
printf("%d\n", ksm(2, len - sucins - big));
}

inline void Solve2(int l, int r) {
len = r - l + 1; big = 0;
for(int i = 1; i <= cnt && prime[i] <= r; i++) big += (r / prime[i]) != ((l - 1) / prime[i]);
printf("%d\n", ksm(2, len - big));
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
T = read();
rep(i, 1, T) l[i] = read(), r[i] = read(), n = max(n, r[i]);
PreSolve();
rep(i, 1, T) {
if(r[i] - l[i] + 1 > 6000) Solve2(l[i], r[i]);
else Solve1(l[i], r[i]);
}
return 0;
}

换桌

直接题意连边好像有\(70pts\)

考虑优化一下,显然可以直接线段树优化区间连边,这个地方有个绝对值的话直接用两颗线段树就好了。(桌子外和桌子内)这样的话边数是两个 log 的。应该过不了\(100pts\)

然后因为对于每张桌子内部没有区间限制,所以直接对于每个桌子把它内部连成一个环就好了,边权为\(1\)。这样就完美的将问题解决了。

边数\(O(nm \log {nm})\),点数\(O(nm)\)。然后跑个费用流就好了。

实际上像这样的位置关系都可拆成若干条费用为\(1\)的边来跑,有时还是可以大大减少边的数量的。

代码:

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
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
/*
* 2979.cpp
* This file is part of 2979
*
* Copyright (C) 2019 - ViXbob
*
* 2979 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 2979 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 2979. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))
#define id(x, y) ((x - 1) * m + y)
#define pre(x) (x == 1 ? m : x - 1)
#define suc(x) (x == m ? 1 : x + 1)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 2e4 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;
const int maxm = 1e6 + 5;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int n, m, L[maxn][15], R[maxn][15], tot;

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}

namespace NetFlow {
int MinCost, MaxFlow, head[maxn], cnt = 1;
int dis[maxn], delta, S, T, vis[maxn];

struct Graph {
int fr, to, nt, f, w;
Graph(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0) {
fr = a; to = b; nt = c; f = d; w = e;
}
} e[maxm << 1];

inline void add(int x, int y, int f, int w) {
e[++cnt] = Graph(x, y, head[x], f, w); head[x] = cnt;
e[++cnt] = Graph(y, x, head[y], 0, -w); head[y] = cnt;
}

inline void Reduce() {
rep(i, 2, cnt) e[i].w += dis[e[i].to] - dis[e[i].fr];
delta += dis[S];
}

inline bool SPFA() {
queue<int> q;
static bool inq[maxn];
memset(dis, 0x3f, sizeof(int) * (tot + 5));
memset(inq, 0, sizeof(bool) * (tot + 5));
q.push(T); inq[T] = 1; dis[T] = 0;
while(q.size()) {
int u = q.front(); q.pop(); inq[u] = 0;
for(int i = head[u]; i; i = e[i].nt) {
int v = e[i].to, f = e[i ^ 1].f, w = e[i ^ 1].w;
if(dis[v] > dis[u] + w && f > 0) {
dis[v] = dis[u] + w;
if(!inq[v]) inq[v] = 1, q.push(v);
}
}
} return dis[S] != dis[0];
}

inline bool Dijkstra() {
priority_queue<pair<int, int> > q;
memset(dis, 0x3f, sizeof(int) * (tot + 5));
q.push(mp(dis[T] = 0, T));
while(q.size()) {
int u = q.top().second, now = -q.top().first; q.pop();
if(dis[u] != now) continue;
for(int i = head[u]; i; i = e[i].nt) {
int v = e[i].to, f = e[i ^ 1].f, w = e[i ^ 1].w;
if(dis[v] > dis[u] + w && f > 0) {
dis[v] = dis[u] + w;
q.push(mp(-dis[v], v));
}
}
} return dis[S] != dis[0];
}

inline int dfs(int x, int flow) {
if(x == T || flow <= 0) return flow;
vis[x] = 1; int used = 0;
for(int i = head[x]; i; i = e[i].nt) {
int v = e[i].to, w = e[i].w, f = e[i].f;
if(f > 0 && w == 0 && !vis[v]) {
int tmp = dfs(v, min(flow, f));
flow -= tmp; used += tmp;
e[i].f -= tmp; e[i ^ 1].f += tmp;
if(flow <= 0) break;
}
} return used;
}

inline void Augment() {
int CurFlow = 0;
memset(vis, 0, sizeof(int) * (tot + 5));
if(CurFlow = dfs(S, inf)) {
MaxFlow += CurFlow;
MinCost += CurFlow * delta;
memset(vis, 0, sizeof(int) * (tot + 5));
}
}

inline void PrimalDual() {
if(!SPFA()) return;
Reduce(); Augment();
while(Dijkstra()) Reduce(), Augment();
}
}

using NetFlow :: S;
using NetFlow :: T;
using NetFlow :: add;

#define ls p << 1
#define rs p << 1 | 1
#define mid (l + r >> 1)
struct SGT {
int id[305 * 4], col, ty;

inline void Build(int l, int r, int p) {
id[p] = ++tot;
if(l == r) return add(id[p], id(r, col) + n * m, inf, ty * r);
Build(l, mid, ls); Build(mid + 1, r, rs);
add(id[p], id[ls], inf, 0);
add(id[p], id[rs], inf, 0);
}

inline void Link(int l, int r, int ql, int qr, int p, int x, int w) {
if(ql > qr || l > ql || r < qr) return;
if(l == ql && r == qr) return add(x, id[p], inf, 2 * w);
if(qr <= mid) Link(l, mid, ql, qr, ls, x, w);
else if(ql > mid) Link(mid + 1, r, ql, qr, rs, x, w);
else Link(l, mid, ql, mid, ls, x, w), Link(mid + 1, r, mid + 1, qr, rs, x, w);
}
} Tree[25];
#undef ls
#undef rs
#undef mid

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); m = read();
rep(i, 1, n) rep(j, 1, m) L[i][j] = read() + 1;
rep(i, 1, n) rep(j, 1, m) R[i][j] = read() + 1;
S = 2 * n * m + 1; T = S + 1; tot = T;
rep(i, 1, n) rep(j, 1, m) add(S, id(i, j), 1, 0), add(id(i, j) + n * m, T, 1, 0);
rep(i, 1, n) rep(j, 1, m) {
add(id(i, j) + n * m, id(i, pre(j)) + n * m, inf, 1);
add(id(i, j) + n * m, id(i, suc(j)) + n * m, inf, 1);
}
rep(i, 1, m) {
Tree[i].col = Tree[i + m].col = i;
Tree[i].ty = -2; Tree[i + m].ty = 2;
Tree[i].Build(1, n, 1); Tree[i + m].Build(1, n, 1);
}
rep(i, 1, n) rep(j, 1, m) {
if(R[i][j] <= i) Tree[j].Link(1, n, L[i][j], R[i][j], 1, id(i, j), i);
else if(L[i][j] >= i) Tree[j + m].Link(1, n, L[i][j], R[i][j], 1, id(i, j), -i);
else {
Tree[j].Link(1, n, L[i][j], i, 1, id(i, j), i);
Tree[j + m].Link(1, n, i, R[i][j], 1, id(i, j), -i);
}
}
// cerr << tot << endl;
NetFlow :: PrimalDual();
if(NetFlow :: MaxFlow != n * m) { puts("no solution"); return 0; }
cout << NetFlow :: MinCost << endl;
return 0;
}

大魔法师

线段树上的每个节点都存一个\(1 \times 4\)的矩阵维护这个子树的\(A,B,C\)的和,和这个子树的区间长度就好了。转移矩阵显然。复杂度为\(O(4^3 n\log n)\)。可能需要卡一下常,否则一不小心就\(100\)\(30\)

不是很懂为啥矩阵转移就可以直接维护\(6\)操作而不能直接搞,求聚聚解答一下这两个的本质区别。

用矩阵来维护转移好像比较有启发意义?(对我这个蒟蒻来说)

代码:

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
/*
* 2980.cpp
* This file is part of 2980
*
* Copyright (C) 2019 - ViXbob
*
* 2980 is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* 2980 is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with 2980. If not, see <http://www.gnu.org/licenses/>.
*/

/**
* There is no end though there is a start in space. ---Infinity.
* It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
* Only the person who was wisdom can read the most foolish one from the history.
* The fish that lives in the sea doesn't know the world in the land.
* It also ruins and goes if they have wisdom.
* It is funnier that man exceeds the speed of light than fish start living in the land.
* It can be said that this is an final ultimatum from the god to the people who can fight.
*
* Steins;Gate
*/
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 2e5 + 5e4 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
while(isdigit(ch)) { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int n, a[maxn], b[maxn], c[maxn], m;
bool Htag[maxn << 2];

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
return rnt;
}

struct Matrix {
int mat[4][4], H, W;
Matrix(int a = 0, int b = 0) {
H = a; W = b;
rep(i, 0, H - 1) rep(j, 0, W - 1) mat[i][j] = 0;
}
Matrix operator * (const Matrix &t) const {
Matrix rnt(H, t.W);
assert(W == t.H);
rep(i, 0, H - 1) rep(j, 0, t.W - 1) rep(k, 0, W - 1)
rnt.mat[i][j] = pls(rnt.mat[i][j], 1ll * mat[i][k] * t.mat[k][j] % P);
return rnt;
}

Matrix operator + (const Matrix &t) const {
Matrix rnt(H, W);
assert(H == t.H && W == t.W);
rep(i, 0, H - 1) rep(j, 0, W - 1)
rnt.mat[i][j] = pls(mat[i][j], t.mat[i][j]);
return rnt;
}

inline void print() {
cerr << H << " " << W << endl;
rep(i, 0, H - 1) {
rep(j, 0, W - 1) cerr << mat[i][j] << " ";
cerr << endl;
}
cerr << endl;
}
} t[maxn << 2], tag[maxn << 2], I, f;

#define ls p << 1
#define rs p << 1 | 1
#define mid (l + r >> 1)
inline void Build(int l, int r, int p) {
tag[p] = I; Htag[p] = 0; t[p] = Matrix(1, 4);
if(l == r) {
t[p].mat[0][0] = a[r];
t[p].mat[0][1] = b[r];
t[p].mat[0][2] = c[r];
t[p].mat[0][3] = 1;
return;
}
Build(l, mid, ls); Build(mid + 1, r, rs);
t[p] = t[ls] + t[rs];
}

inline void pushtag(int p, Matrix &x) {
t[p] = t[p] * x;
tag[p] = tag[p] * x;
Htag[p] = 1;
}

inline void pushdown(int p) {
if(Htag[p]) {
pushtag(ls, tag[p]);
pushtag(rs, tag[p]);
Htag[p] = 0; tag[p] = I;
}
}

inline void modify(int l, int r, int ql, int qr, int p, Matrix &x) {
if(l == ql && r == qr) return pushtag(p, x);
pushdown(p);
if(qr <= mid) modify(l, mid, ql, qr, ls, x);
else if(ql > mid) modify(mid + 1, r, ql, qr, rs, x);
else modify(l, mid, ql, mid, ls, x), modify(mid + 1, r, mid + 1, qr, rs, x);
t[p] = t[ls] + t[rs];
}

inline Matrix query(int l, int r, int ql, int qr, int p) {
if(l == ql && r == qr) return t[p];
pushdown(p);
if(qr <= mid) return query(l, mid, ql, qr, ls);
else if(ql > mid) return query(mid + 1, r, ql, qr, rs);
else return query(l, mid, ql, mid, ls) + query(mid + 1, r, mid + 1, qr, rs);
}
#undef ls
#undef rs
#undef mid

int main() {
// freopen("2.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read();
rep(i, 1, n) a[i] = read(), b[i] = read(), c[i] = read();
I = Matrix(4, 4);
rep(i, 0, 3) I.mat[i][i] = 1;
Build(1, n, 1);
m = read();
rep(i, 1, m) {
int opt = read(), l = read(), r = read(); f = I;
assert(f.W == 4 && f.H == 4);
if(opt == 1) f.mat[1][0] = 1;
else if(opt == 2) f.mat[2][1] = 1;
else if(opt == 3) f.mat[0][2] = 1;
else if(opt == 4) f.mat[3][0] = read();
else if(opt == 5) f.mat[1][1] = read();
else if(opt == 6) f.mat[2][2] = 0, f.mat[3][2] = read();
if(opt != 7) modify(1, n, l, r, 1, f);
else {
Matrix rnt = query(1, n, l, r, 1);
printf("%d %d %d\n", rnt.mat[0][0], rnt.mat[0][1], rnt.mat[0][2]);
}
}
return 0;
}