做题计划

老了, 写不动题解了. 如果有很好的题目可能会专门开一篇, 否则就一句话题解吧. (大雾

异或粽子

区间异或和转为前缀异或和, 对于每个右端点维护一个最大值(优先队列维护). 因为不能重复选, 所以要支持删除和查询异或最大值, 用可持久化\(01Trie\)实现就好了. 复杂度\(O(klogn)\)

春节十二响

不难猜到链上的情况可以拓展到树上, 并且两个子树是互不影响的. 对于每个节点维护一个子树中的最优答案, 每次合并儿子节点的子树时就启发式合并. 复杂度\(O(nlog^2n)\)

字符串问题

大家应该都会\(O(n^2)\)的连边然后最长链. 考虑一个字串是另一个字串的前缀, 就是反串的\(parent\)树上的祖先关系. 考虑\(SAM\)优化建图, 每次倍增定位状态. 因为会有\(|A| \le |B|\)的情况, 对于把每个\(parent\)树上的节拆一下, 只拆存在的节点就好了.复杂度\(O(nlogn)\). 清数组的注意复杂度问题.

数树

挺好的一道计数题, 题解见Link

梦美与线段树

线段树模板题, 实际上要求的就是 \(\sum _ {i = 1} ^ n \frac{sum_i^2}{\sum _ {i = 1}^{n}sum_i}\) , 考虑把一段区间都加上一个值, 相当把线段树上的一个子树的每个节点加上其子树大小乘权值, 把式子拆一下, 维护一个\(w^2\)和, \(siz^2\)和, \(siz \cdot w\) 和, \(w\)和就好了. 复杂度 \(O(nlogn)\)

K远点对

\(\textbf{KD-Tree}\)模板题, 用一个子树的可能最远距离去剪枝, 然后用一个堆维护\(K\)

SJY摆棋子

正解\(\textbf{CDQ}\), 但是是一道练习\(\textbf{KD-Tree}\)的好题, 用可能最近曼哈顿距离去剪枝

简单题

如果\(\textbf{KD-Tree}\)中节点为维护的矩形和查询的矩形有交则递归, 否则判断是包含还是完全没交

最长双回文串

\(\textbf{PAM}\)模板题, 正着插入一遍记录以某个字符结尾的最长回文串, 反着同理. 然后扫一遍取\(\max\), 注意两个串都不能是空串. 复杂度\(O(n)\)

选圆圈

将一个圆看成一个正方形, 以此判断是否有交来剪枝. 由于这样可能会被卡, 我们将坐标系随机旋转一个角度, 点就是随机的了. 期望复杂度 \(O(nlogn)​\)

按位或

\(\textbf{min-max}\)容斥模板题, 见Link

重返现世

\(\textbf{kth-min-max}\) 容斥模板题, 见Link

生成魔咒

考虑往 \(\textbf{SAM}\) 上插入一个字符后, 对本质不同的字串个数的影响其实就是 \(maxlen[fa[lst]] - maxlen[lst]\), 就算插入过程中 \(slipt\) 了一个节点, 但并不会影响答案. 注意这题字符集很大, 拿 \(map\) 维护一下 \(trans\) 就好了

与或和

还是考虑分别考虑每一位, 然后这道题的本质就变成了求全是一的子矩阵的个数. 分别考虑每一列, 设\(a_i\)为对于这一列的第\(i\)行最多向前延伸的格数, 并且使得这些格子都是一, 则问题变成求下式 : \[ \sum _ {i = 1} ^ n\sum_{j = i} ^ n\min_{i \le k \le j}\{a_k\} \] 单调栈维护一下就好了

网络

\(\textbf{LCT}\) 傻逼题

巧克力王国

转换一下式子, 每一次询问相当于求一条直线一侧的点的点权和, 直接上\(\text{KD-Tree}\)就好了.

具体的, 我们可以判断直线和\(\text{KD-Tree}\)上每个节点维护的矩形有没有交来进行剪枝.

代码:

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
#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 sqr(x) ((double)(x) * (x))

typedef long long ll;

using namespace std;

const int maxn = 5e4 + 5;
const double eps = 1e-10;

int n, m, D;
ll sum0[maxn], sum1[maxn], A, B, C;
int pos0[maxn], pos1[maxn];

#define equ(x, y) (fabs(x - y) <= eps)

struct Point {
int x[2]; int w;
Point(int a = 0, int b = 0, int c = 0) { x[0] = a; x[1] = b; w = c; }
bool operator < (const Point &t) const { return x[D] < t.x[D] || (equ(x[D], t.x[D]) && x[D ^ 1] < t.x[D ^ 1]); }
} a[maxn], tmp;

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;
}

namespace KDT {
#define mid (l + r >> 1)
struct Node {
Node *ls, *rs;
int mxx, mnx, mxy, mny, x, y;
ll sw, w;
Node(int a = 0, int b = 0, int c = 0) { x = a; y = b; w = c; ls = rs = NULL; }

inline void pushup(Node* &t) {
mxx = max(mxx, t -> mxx);
mnx = min(mnx, t -> mnx);
mxy = max(mxy, t -> mxy);
mny = min(mny, t -> mny);
sw += t -> sw;
}

inline void update() {
mxx = mnx = x;
mxy = mny = y;
sw = w;
if(ls) pushup(ls);
if(rs) pushup(rs);
}

inline void print() { cerr << "x = " << x << ", y = " << y << endl; }

inline int CheckLine() {
ll Mx = max(mxx * A, mnx * A) + max(mxy * B, mny * B);
ll Mn = min(mxx * A, mnx * A) + min(mxy * B, mny * B);
if(Mx < C) return 1; if(Mn >= C) return 0;
return 2;
}
} *root;

inline Node* Build(int l, int r, bool type) {
if(l > r) return NULL;
D = type; nth_element(a + l, a + mid, a + r + 1);
Node *rnt = new Node(a[mid].x[0], a[mid].x[1], a[mid].w);
rnt -> ls = Build(l, mid - 1, type ^ 1);
rnt -> rs = Build(mid + 1, r, type ^ 1);
rnt -> update(); return rnt;
}

inline ll query(Node* &t, ll rnt = 0) {
if(t == NULL) return 0;
if(1ll * t -> x * A + 1ll * t -> y * B < C) rnt += t -> w;
if(t -> ls) {
int type = t -> ls -> CheckLine();
if(type <= 1) rnt += type * t -> ls -> sw;
else rnt += query(t -> ls);
}
if(t -> rs) {
int type = t -> rs -> CheckLine();
if(type <= 1) rnt += type * t -> rs -> sw;
else rnt += query(t -> rs);
} return rnt;
}
}

int main() {
n = read(); m = read();
rep(i, 1, n) {
a[i].x[0] = read(); a[i].x[1] = read();
a[i].w = read();
}
KDT :: root = KDT :: Build(1, n, 0);
rep(i, 1, m) {
A = read(); B = read(); C = read();
printf("%lld\n", KDT :: query(KDT :: root));
}
return 0;
}
/*
3 1
1 2 5
3 1 4
2 2 1
1 1 4
*/

Slay the Spire

考虑一个性质: 在保证能选一张攻击牌的情况下, 剩下的选择强化牌一定比选择攻击牌更优.

证明: 因为每张强化牌的权值大于\(\text{1}\), 并且被选出的攻击牌一定是最大的, 所以将已选出的攻击牌的和翻倍一定比再选一张攻击牌优.

知道上述性质, 我们将攻击牌和强化牌都降序排序, 就可以直接\(\text{dp}\)了.

\(p[i]\)为第\(i\)张强化牌上的数值, \(w[i]\)为第\(i\)张攻击牌上的数值

\(\text{f[i][j][0/1]}\)表示考虑了前\(\text{i}\)张牌选了\(\text{j}\)张牌第\(\text{i}\)张牌有没有用的所有方案的乘积和

\(\text{g[i][j][0/1]}\)表示考虑了前\(\text{i}\)张牌用了\(\text{j}\)张牌第 \(\text{i}\) 张牌有没有用的所有方案的和

很显然我们不会用超过\(k-1\)张强化牌但是我们会选超过\(k-1\)张强化牌, 所以对于\(j \le k-1\)的情况有转移: \[ \begin{aligned}f[i][j][0] \leftarrow& f[i-1][j][0]+f[i-1][j][1]\\f[i][j][1]\leftarrow& (f[i-1][j-1][0]+f[i-1][j-1][1])\times p[i]\end{aligned} \] 对于\(j \ge k\)的情况, 设\(F[i][j]\)表示考虑前\(i\)张选了\(j\)张强化牌用了\(k-1\)张的所有方案的乘积的和, 则有转移: \[ \begin{aligned}F[i][j] \leftarrow F[i-1][j] + f[i][k-1][1] \times \binom{n - i}{j - k + 1}\end{aligned} \] 对于\(g\)有转移: \[ \begin{aligned}g[i][j][0]\leftarrow& g[i-1][j][0]+g[i-1][j][1]\\g[i][j][1]\leftarrow& g[i-1][j-1][0]+g[i-1][j-1][1]+\binom{i-1}{j-1}\times w[i]\end{aligned} \] 最后我们枚举一下选了多少张强化牌, 就可以直接计算答案了

代码:

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
#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 sqr(x) ((double)(x) * (x))
#define inv(x) (ksm(x, P - 2))

typedef long long ll;

using namespace std;

const int maxn = 3e3 + 15;
const int P = 998244353;

int n, m, k, T, f[maxn][maxn][2], fac[maxn], ifac[maxn], p[maxn], w[maxn], g[maxn][maxn][2], ans;
int F[maxn], G[maxn];

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;
}

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 mul(int a, int b, int c) { return 1ll * a * b % P * c % P; }
inline int mul(int a, int b, int c, int d) { return 1ll * a * b % P * c % P * d % P; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = mul(x, x)) if(i & 1) rnt = mul(rnt, x);
return rnt;
}
inline int C(int n, int m) { return n >= m ? mul(fac[n], ifac[m], ifac[n - m]) : 0; }

int main() {
T = read(); fac[0] = 1;
rep(i, 1, maxn - 1) fac[i] = mul(fac[i - 1], i);
ifac[maxn - 1] = inv(fac[maxn - 1]);
dep(i, maxn - 2, 0) ifac[i] = mul(ifac[i + 1], i + 1);
while(T--) {
n = read(); m = read(); k = read(); ans = 0;
rep(i, 1, n) p[i] = read();
rep(i, 1, n) w[i] = read();
sort(p + 1, p + 1 + n, greater<int>());
sort(w + 1, w + 1 + n, greater<int>());
memset(F, 0, sizeof(F)); memset(f, 0, sizeof(f));
memset(G, 0, sizeof(G)); memset(g, 0, sizeof(g));
f[0][0][0] = 1;
rep(i, 1, n) {
f[i][0][0] = 1;
rep(j, 1, min(k, i)) {
f[i][j][0] = pls(f[i - 1][j][0], f[i - 1][j][1]);
f[i][j][1] = mul(p[i], pls(f[i - 1][j - 1][0], f[i - 1][j - 1][1]));
g[i][j][0] = pls(g[i - 1][j][0], g[i - 1][j][1]);
g[i][j][1] = pls(pls(g[i - 1][j - 1][0], g[i - 1][j - 1][1]), mul(C(i - 1, j - 1), w[i]));
}
if(i >= k - 1)
rep(j, k, min(m, n)) F[j] = pls(F[j], mul(f[i][k - 1][1], C(n - i, j - k + 1)));
}
rep(i, 0, k - 1) F[i] = pls(f[n][i][0], f[n][i][1]);
if(k == 1) rep(i, 0, m) F[i] = C(n, i);
// rep(i, 0, m) cerr << "F[" << i << "] = " << F[i] << endl;
// rep(i, 0, m) cerr << "G[" << i << "] = " << G[i] << endl;
rep(i, 0, m) {
int Gi = k - min(k - 1, i), tot = m - i;
if(tot > n) continue;
int p = 0;
rep(j, 1, n) p = pls(p, mul(g[j][Gi][1], C(n - j, tot - Gi)));
ans = pls(ans, mul(p, F[i]));
}
cout << ans << endl;
}
return 0;
}
/*
*/

猎人杀

喵喵妙妙题, 见Link

Minimax

直接维护每个节点是其子树中的每个叶子节点的权值的概率.

设我们现在处理到第\(x\)个节点, \(f_i, g_i, F_i\)表示左右儿子,\(x\)是权值\(i\)的概率, 若\(i\)在左儿子则有: \[ F_i = f_i\left(p_x\sum _ {j = 1} ^ {i}g_j+(1-p_x)\sum_{j = i}^{m}g_j\right) \] 右儿子同理.

然后离散权值, \(\text{dfs}\)的时候线段树合并一下就好了.

具体的维护一个乘法标记和子树概率和, 在合并两颗线段树的时候对于两颗线段树分别维护大于小于当前节点的另一颗线段树上的概率和就好了.

代码:

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
#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 sqr(x) ((double)(x) * (x))
#define inv(x) (ksm(x, P - 2))
#define To(x) (x ? x : 1)

typedef long long ll;

using namespace std;

const int maxn = 3e5 + 5;
const int LOG = 35;
const int P = 998244353, G = 3;

int n, w[maxn], ch[maxn][2], pos[maxn], tot, RNG;

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;
}

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 mul(int a, int b, int c) { return 1ll * a * b % P * c % P; }
inline int mul(int a, int b, int c, int d) { return 1ll * a * b % P * c % P * d % P; }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = mul(x, x)) if(i & 1) rnt = mul(rnt, x);
return rnt;
}

const int inv = inv(1e4);

namespace SEG {
#define mid (l + r >> 1)
#define Rs(x) (t[x].rs)
#define Ls(x) (t[x].ls)
int root[maxn], cnt;
struct Node {
int ls, rs, sum, siz, mtag;
Node() { ls = rs = sum = siz = 0; mtag = 1; }
} t[maxn * 10];

inline void insert(int l, int r, int pos, int &p, int x) {
if(!p) p = ++cnt;
t[p].sum = pls(t[p].sum, x); t[p].siz++;
if(l == r) return;
if(pos <= mid) insert(l, mid, pos, t[p].ls, x);
else insert(mid + 1, r, pos, t[p].rs, x);
}

inline void pushmtag(int p, int x) {
if(x == 0) return;
t[p].mtag = mul(t[p].mtag, x);
t[p].sum = mul(t[p].sum, x);
}

inline void pushup(int p) {
if(!p) return;
t[p].siz = t[Ls(p)].siz + t[Rs(p)].siz;
t[p].sum = pls(t[Ls(p)].sum, t[Rs(p)].sum);
}

inline void pushdown(int p) {
if(t[p].mtag != 1) {
pushmtag(t[p].ls, t[p].mtag);
pushmtag(t[p].rs, t[p].mtag);
t[p].mtag = 1;
}
}

inline int merge(int l, int r, int u, int p, int suc, int Lmx, int Rmx, int Lmn, int Rmn) {
if(!u || !p) {
if(u) pushmtag(u, pls(mul(Lmx, dec(1, suc)), mul(Lmn, suc)));
else pushmtag(p, pls(mul(Rmx, dec(1, suc)), mul(Rmn, suc)));
return u + p;
}
pushdown(u); pushdown(p);
int Lls = t[Ls(u)].sum, Lrs = t[Rs(u)].sum, Rls = t[Ls(p)].sum, Rrs = t[Rs(p)].sum;
int LS = merge(1, mid, t[u].ls, t[p].ls, suc, pls(Lmx, Rrs), pls(Rmx, Lrs), Lmn, Rmn);
int RS = merge(mid + 1, r, t[u].rs, t[p].rs, suc, Lmx, Rmx, pls(Lmn, Rls), pls(Rmn, Lls));
t[u].ls = LS; t[u].rs = RS;
pushup(u); return u;
}

inline int calc(int l, int r, int p, int rnt = 0) {
if(!p) return 0;
if(l == r) {
RNG = pls(RNG, t[p].sum);
return mul(r, pos[r], mul(t[p].sum, t[p].sum));
}
pushdown(p);
rnt = pls(rnt, calc(l, mid, Ls(p)));
rnt = pls(rnt, calc(mid + 1, r, Rs(p)));
return rnt;
}
#undef Rs
#undef Ls
#undef mid
}

inline int dfs(int x, int L = 0, int R = 0) {
if(!x) return 0;
if(!ch[x][0]) {
int p = lower_bound(pos + 1, pos + 1 + tot, w[x]) - pos;
SEG :: insert(1, tot, p, SEG :: root[x], 1);
return SEG :: root[x];
}
L = dfs(ch[x][0]); R = dfs(ch[x][1]);
if(!R) return L;
int RNT = SEG :: merge(1, tot, L, R, w[x], 0, 0, 0, 0);
return RNT;
}

int main() {
n = read();
rep(i, 1, n) {
int fa = read();
if(fa) ch[fa][ch[fa][0] > 0] = i;
}
rep(i, 1, n) {
w[i] = read();
if(ch[i][0]) w[i] = mul(w[i], inv);
else pos[++tot] = w[i];
}
sort(pos + 1, pos + 1 + tot);
int root = dfs(1);
cout << SEG :: calc(1, tot, root) << endl;
return 0;
}
/*
5
0 1 1 2 2
2500 2500 2 1 3
*/

随机算法

首先大家肯定都会一个\(n \cdot 3^n\)的暴力. 直接记录每个节点的三个状态然后进行转移.

但是考虑到被选中但不在独立集内, 和根本没有被选中的点其实是等价的, 所以我们设计状态\(f[i][S]\)表示考虑了前\(i\)个节点, 独立集的集合为\(S\)的方案数.

转移可以这样考虑, 如果一个点可以被选入独立集则直接转移, 否则乘上\(i \sim 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
#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 sqr(x) ((double)(x) * (x))
#define inv(x) (ksm(x, P - 2))
#define To(x, y, z) (x | y << 20 | z << 40)
#define popcount(x) __builtin_popcount(x)

typedef long long ll;

using namespace std;

const int maxn = 25;
const int P = 998244353;

int n, m, fac[maxn], top[2], G[maxn], nt[1 << 20], U, Mx, ifac[maxn];
int f[1 << 20][maxn], siz[1 << 20], ans, g[1 << 20];

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;
}

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline void add(int &x, int y) { x += y; 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 mul(int a, int b, int c) { return 1ll * a * b % P * c % P; }
inline int mul(int a, int b, int c, int d) { return 1ll * a * b % P * c % P * d % P; }
inline int A(int n, int m) { return mul(fac[n], ifac[n - m]); }
inline int ksm(int x, int k, int rnt = 1) {
for(int i = k; i; i >>= 1, x = mul(x, x)) if(i & 1) rnt = mul(rnt, x);
return rnt;
}

int main() {
// freopen("1.in", "r", stdin);
n = read(); m = read(); fac[0] = 1; U = (1 << n) - 1;
rep(i, 1, maxn - 1) fac[i] = mul(fac[i - 1], i);
ifac[maxn - 1] = inv(fac[maxn - 1]);
dep(i, maxn - 2, 0) ifac[i] = mul(ifac[i + 1], i + 1);
// rep(i, 0, maxn - 1) cerr << fac[i] << " " << ifac[i] << endl;
rep(i, 1, m) {
int x = read(), y = read();
G[x] |= 1 << y - 1;
G[y] |= 1 << x - 1;
}
rep(i, 1, 20) nt[1 << i - 1] = i;
rep(i, 1, U) nt[i] = nt[i & -i];
rep(i, 1, U) siz[i] = siz[i >> 1] + (i & 1);
f[0][0] = 1;
rep(i, 0, n - 1) rep(S, 0, U) if(f[S][i]) {
// cerr << i << " " << S << endl;
// cerr << "f[" << S << "][" << i << "] = " << f[S][i] << endl;
int tmp = U & ~S, cnt = 0;
for(int k = nt[tmp]; k; k = nt[tmp &= ~(1 << k - 1)]) {
if(G[k] & S) cnt++;
else add(f[S | 1 << k - 1][i + 1], f[S][i]);
}
add(f[S][i + 1], mul(f[S][i], cnt - (i - siz[S])));
}
rep(S, 0, U) if(f[S][n]) {
// cerr << f[S][n] << endl;
if(siz[S] > Mx) Mx = siz[S], ans = f[S][n];
else if(siz[S] == Mx) ans = pls(ans, f[S][n]);
} cout << mul(ans, ifac[n]) << endl;
return 0;
}
/*
*/

铁人两项

因为要求的是简单路径. 所以考虑建出圆方树后, 枚举一个中间点(一定是圆点), 另外的起点和终点要么是在同一个子树, 要么不在同一个子树所以直接分两种情况分别讨论一下就好了.

注意图可能不连通(毒瘤啊)

代码:

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
#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 son(x, y) (dfn[y] < dfn[x] ? SIZE(V) - size[x] : size[y])
#define sqr(x) (1ll * (x) * (x))

using namespace std;

typedef long long ll;

const int maxn = 3e5 + 5;
const int inf = 0x3f3f3f3f;

int n, m, Q, w[maxn], dfn[maxn], low[maxn], st[maxn], top, coc, tot;
ll sum[maxn], ans, N;
vector<int> G[maxn], E[maxn], V;

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;
}

inline void add(int x, int y, vector<int>* G) { G[x].push_back(y); G[y].push_back(x); }

inline void Tarjan(int x) {
V.push_back(x);
dfn[x] = low[x] = ++coc; st[++top] = x;
rep(i, 0, SIZE(G[x]) - 1) {
int v = G[x][i];
if(!dfn[v]) {
Tarjan(v); low[x] = min(low[x], low[v]);
if(low[v] >= dfn[x]) {
add(x, ++tot, E); int u = x;
do { u = st[top--]; add(u, tot, E); } while(u != v);
}
} else low[x] = min(low[x], dfn[v]);
}
}

int fa[maxn], size[maxn];

inline void dfs(int x) {
size[x] = (x <= n); dfn[x] = ++dfn[0];
rep(i, 0, SIZE(E[x]) - 1) {
int v = E[x][i];
if(v == fa[x]) continue;
fa[v] = x;
dfs(v);
size[x] += size[v];
}
}

int main() {
// freopen("1.in", "r", stdin);
tot = n = read(); m = read();
rep(i, 1, m) {
int x = read(), y = read();
G[x].push_back(y);
G[y].push_back(x);
}
rep(i, 1, n) if(!dfn[i]) {
int b = tot;
V.clear(); Tarjan(i);
dfs(V[0]);
if(SIZE(V) < 3) continue;
rep(i, b + 1, tot) rep(j, 0, SIZE(E[i]) - 1) sum[i] += sqr(son(i, E[i][j]));
for(auto i : V) rep(j, 0, SIZE(E[i]) - 1)
ans += 1ll * son(i, E[i][j]) * (SIZE(V) - son(i, E[i][j]) - 1);
// cerr << ans << endl;
for(auto i : V) rep(j, 0, SIZE(E[i]) - 1)
ans += sqr(SIZE(V) - son(E[i][j], i)) - (sum[E[i][j]] - sqr(son(E[i][j], i)));
} cout << ans << endl;
return 0;
}

Tourists

一般要求的是简单路径我们都可通过将原图转化成一颗圆方树进行处理, 所以我们先建出圆方树.

然后将每个方点权值看做与其相连的圆点的权值的最小值就好了, 这个可以拿一个\(\text{multiset}\)维护一下. 然后直接在树上查两个点之间的路径上的最小值就好了, 这个用树剖就可以做.

这样就做完了?

实则有点小问题, 如果是这样的话我们修改一个点的点权后要修改和其相连的所有方点的权值, 一个菊花图就萎了.

实际上这样维护了很多无用的信息, 我们可以直接将每个圆点的权值丢到它方爸爸里面去. 这样就非常优秀了, 没有维护冗杂信息. 每次修改点权的复杂度就变成了\(O(logn)\).但这样要注意查询两点之间的最小值时要把\(\text{lca}\)处的方点的圆爸爸的权值也拿过来更新答案.

复杂度\(O(nlog^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
#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())

using namespace std;

typedef long long ll;

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

int n, m, Q, w[maxn], dfn[maxn], low[maxn], st[maxn], stop, coc, tot;
vector<int> G[maxn], E[maxn];
multiset<int> Mn[maxn];

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;
}

inline void add(int x, int y, vector<int>* G) { G[x].push_back(y); G[y].push_back(x); }

inline void Tarjan(int x) {
dfn[x] = low[x] = ++coc; st[++stop] = x;
rep(i, 0, SIZE(G[x]) - 1) {
int v = G[x][i];
if(!dfn[v]) {
Tarjan(v);
low[x] = min(low[x], low[v]);
if(low[v] >= dfn[x]) {
add(x, ++tot, E); int u = x;
do { u = st[stop--]; add(u, tot, E); } while(u != v);
}
} else low[x] = min(low[x], dfn[v]);
}
}

int dep[maxn], fa[maxn], size[maxn], son[maxn], top[maxn], pos[maxn];

inline void dfs(int x) {
size[x] = 1;
// cerr << "ON " << x << endl;
// cerr << "fa[" << x << "] = " << fa[x] << endl;
rep(i, 0, SIZE(E[x]) - 1) {
int v = E[x][i];
if(v == fa[x]) continue;
fa[v] = x; dep[v] = dep[x] + 1;
dfs(v);
if(x > n) Mn[x].insert(w[v]);
size[x] += size[v];
if(size[v] > size[son[x]]) son[x] = v;
}
if(son[x] == 0) son[x] = x;
// cerr << "son[" << x << "] = " << son[x] << endl;
// cerr << "fa[" << x << "] = " << fa[x] << endl;
}

inline void dfs(int x, int f) {
// cerr << "ON " << x << endl;
dfn[++dfn[0]] = x; pos[x] = dfn[0];
top[x] = f;
if(x != son[x]) dfs(son[x], f);
rep(i, 0, SIZE(E[x]) - 1) {
int v = E[x][i];
if(v == fa[x] || v == son[x]) continue;
dfs(v, v);
}
}

namespace SEG {
#define ls p << 1
#define rs p << 1 | 1
#define mid (l + r >> 1)
struct Node {
int mn;
Node() { mn = inf; }
} t[maxn << 2];

inline void Build(int l, int r, int p) {
if(l == r) return (void)(t[p].mn = dfn[r] > n ? *Mn[dfn[r]].begin() : w[dfn[r]]);
Build(l, mid, ls); Build(mid + 1, r, rs);
t[p].mn = min(t[ls].mn, t[rs].mn);
}

inline void modify(int l, int r, int pos, int x, int p) {
if(l == r) return (void)(t[p].mn = x);
if(pos <= mid) modify(l, mid, pos, x, ls);
else modify(mid + 1, r, pos, x, rs);
t[p].mn = min(t[ls].mn, t[rs].mn);
}

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

inline int ChainQuery(int x, int y, int rnt = inf) {
while(top[x] != top[y]) {
if(dep[top[x]] < dep[top[y]]) swap(x, y);
rnt = min(rnt, SEG :: query(1, tot, pos[top[x]], pos[x], 1));
// cerr << x << " " << top[x] << endl;
// cerr << rnt << endl;
x = fa[top[x]];
}
if(dep[x] > dep[y]) swap(x, y);
// cerr << x << " " << y << endl;
rnt = min(rnt, SEG :: query(1, tot, pos[x], pos[y], 1));
// cerr << rnt << endl;
if(x > n) rnt = min(rnt, w[fa[x]]);
return rnt;
}

int main() {
// freopen("1.in", "r", stdin);
tot = n = read(); m = read(); Q = read();
rep(i, 1, n) w[i] = read();
rep(i, 1, m) {
int x = read(), y = read();
G[x].push_back(y);
G[y].push_back(x);
}
rep(i, 1, n) if(!dfn[i]) Tarjan(i);
// cerr << "Tarjan OK!" << endl;
dfs(1); dfs(1, 1);
// cerr << "Chain OK!" << endl;
// cerr << *Mn[4].begin() << endl;
SEG :: Build(1, tot, 1);
rep(i, 1, Q) {
char opt[5]; int x, y;
scanf("%s%d%d", opt + 1, &x, &y);
if(opt[1] == 'A') printf("%d\n", ChainQuery(x, y));
else {
if(fa[x]) {
Mn[fa[x]].erase(Mn[fa[x]].find(w[x]));
Mn[fa[x]].insert(y);
SEG :: modify(1, tot, pos[fa[x]], *Mn[fa[x]].begin(), 1);
}
w[x] = y; SEG :: modify(1, tot, pos[x], w[x], 1);
// cerr << y << endl;
}
}
return 0;
}

聚会

一道有趣的交互题, 直接做自闭了.

考虑直接固定两个端点\(u, v​\), 然后依次询问其他的节点, 我们一定可以把属于这两个节点的之间的这条路径上的点给抽出来, 并且知道每个点是在哪个子树, 如图:

直接把每个节点的子树和\(u, v\)这条链上的节点看成若干颗新的树, 递归处理就好了. 如果树的大小小于等于二就可以直接\(\text{Bridge}\)了.

关于复杂度, 因为我们可以随机两个端点\(u, v\)所以在期望意义下最大的子树大小不超过整棵树的\(\frac{1}{2}\), 所以最多递归\(logn\)层, 每层\(O(n)\).期望复杂度\(O(nlogn)\).

代码:

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
#include <bits/stdc++.h>
#include "meetings.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 sqr(x) ((double)(x) * (x))
#define inv(x) (ksm(x, P - 2))
#define To(x, y, z) (x | y << 20 | z << 40)
#define popcount(x) __builtin_popcount(x)
#define mp(x, y, z) (make_pair(make_pair(x, y), z))

typedef long long ll;

using namespace std;

const int maxn = 2e3 + 5;

int con, sum, n, vis[maxn];

inline int rand_(int l, int r) { return l + rand() % (r - l + 1); }

map<pair<pair<int, int>, int>, int> MP;
vector<int> son[maxn];

inline int query(int a, int b, int c) {
static int d[5];
d[1] = a; d[2] = b; d[3] = c;
sort(d + 1, d + 4);
pair<pair<int, int>, int> tmp = mp(d[1], d[2], d[3]);
if(!MP.count(tmp)) return MP[tmp] = Query(a, b, c);
else return MP[tmp];
}

inline void Solve(vector<int> &tmp) {
if(SIZE(tmp) <= 1) return;
// cerr << SIZE(tmp) << endl;
if(SIZE(tmp) <= 2) {
Bridge(min(tmp[0], tmp[1]), max(tmp[1], tmp[0])); con++;
return;
}
map<int, vector<int> > son;
vector<int> nxt;
random_shuffle(tmp.begin(), tmp.end());
int a = tmp[rand_(0, SIZE(tmp) - 1)], b = tmp[rand_(0, SIZE(tmp) - 1)];
// cerr << "OK" << endl;
// cerr << a << endl;
while(a == b) b = tmp[rand_(0, SIZE(tmp) - 1)];
// cerr << "OK Rand" << endl;
son[a].push_back(a); son[b].push_back(b);
for(int i : tmp) if(i != a && i != b) {
int d = query(a, b, i);
son[d].push_back(i);
}
for(auto i : son) Solve(i.second), nxt.push_back(i.first);
Solve(nxt);
}

void Solve(int N) {
srand(time(NULL));
vector<int> tmp;
rep(i, 0, N - 1) tmp.push_back(i);
n = N; Solve(tmp);
}
/*
*/

战略游戏

建个圆方树. 再建个虚树, 答案就是虚树上圆点的个数.

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
/*
* 5329.cpp
* This file is part of BZOJ5329
*
* Copyright (C) 2019 - ViXbob
*
* BZOJ5329 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.
*
* BZOJ5329 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 BZOJ5329. If not, see <http://www.gnu.org/licenses/>.
*/

// Begin at 2019-04-20 14:31:00 - ViXbob

/**
* 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 dis(x, y) (abs(dep[x] - dep[y]))
using namespace std;

typedef long long ll;

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

int T, n, q, m, k, tot;
vector<int> G[maxn], E[maxn], H[maxn], tmp;

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;
}

inline void add(int x, int y, vector<int> *G) { G[x].push_back(y); G[y].push_back(x); }

int dfn[maxn], low[maxn], st[maxn], stop, coc, point[maxn];
int pos[maxn], size[maxn], fa[maxn][20], dep[maxn], rdep[maxn];

inline void init() {
memset(dfn, 0, sizeof(dfn));
memset(fa, 0, sizeof(int) * (2 * n * 20));
stop = coc = 0;
rep(i, 0, n) G[i].clear();
rep(i, 0, 2 * n) E[i].clear();
}

inline void Tarjan(int x) {
dfn[x] = low[x] = ++coc; st[++stop] = x;
for(auto v : G[x]) {
if(!dfn[v]) {
Tarjan(v); low[x] = min(low[x], low[v]);
if(low[v] >= dfn[x]) {
add(x, ++tot, E); int u = x;// cerr << u << " -> " << tot << endl;
do { u = st[stop--]; add(u, tot, E); } while(u != v);
}
} else low[x] = min(low[x], dfn[v]);
}
}

inline void dfs(int x) {
size[x] = 1; dfn[++dfn[0]] = x;
pos[x] = dfn[0];
for(int i = 1; dep[x] >> i; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
for(auto v : E[x]) {
if(v == fa[x][0]) continue;
dep[v] = dep[x] + 1; fa[v][0] = x;
rdep[v] = rdep[x] + (v <= n);
dfs(v);
size[x] += size[v];
}
}

inline int Jump(int x, int d) {
for(int i = 0; d; d >>= 1, i++) if(d & 1) x = fa[x][i];
return x;
}

inline int LCA(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
x = Jump(x, dep[x] - dep[y]);
if(x == y) return x;
for(int i = 19; ~i; i--)
if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
return fa[x][0];
}

int ans, deg[maxn], vis[maxn];

inline void calc(int x, int y) { ans += rdep[fa[y][0]] - rdep[x]; deg[x]++; deg[y]++; } //cerr << x << " -> " << y << endl; }

inline void push(int x) {
tmp.push_back(x);
if(stop <= 0) return (void)(st[++stop] = x);
int lca = LCA(x, st[stop]);
// cerr << "LCA(" << x << ", " << st[stop] << ") = " << LCA << endl;
if(lca == st[stop]) return (void)(st[++stop] = x);
while(stop > 1 && pos[st[stop - 1]] >= pos[lca]) calc(st[stop - 1], st[stop]), stop--;
if(lca != st[stop]) calc(lca, st[stop]), st[stop] = lca, tmp.push_back(lca);
return (void)(st[++stop] = x);
}

inline void Solve() {
for(int i : tmp) ans += (i <= n && !vis[i]);
// for(int i : tmp) ans -= (deg[i] <= 1);
for(int i : tmp) deg[i] = 0, vis[i] = 0;
printf("%d\n", ans);
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
T = read();
while(T--) {
tot = n = read(); m = read(); init();
rep(i, 1, m) add(read(), read(), G);
Tarjan(1); rdep[1] = 1; dfs(1);
q = read();
while(q--) {
// cerr << "------------------" << endl;
k = read(); tmp.clear();
rep(i, 1, k) vis[point[i] = read()] = 1;
sort(point + 1, point + 1 + k, [](int x, int y) -> bool { return pos[x] < pos[y]; });
stop = 0; ans = 0;
rep(i, 1, k) push(point[i]); //cerr << "point[" << i << "] = " << point[i] << endl;
while(stop > 1) calc(st[stop - 1], st[stop]), stop--;
Solve();
}
}
return 0;
}
/*
*/

消耗战

虚树模板题, 见Link

世界树

虚树模板题, 见Link

大工程

虚树模板题, 见Link

天才黑客

很暴力的一种做法就是直接把一个点\(i\)拆成\(deg_i\)个点, 然后暴力\(\text{Dijkstra}\)这样复杂度最坏是\(O(n^2logn)\)的.

我们考虑优化这个过程, 我们之所以要把一个点拆成入度个点, 是因为转移时在\(\text{Trie}\)上的\(\text{lca}\)不同导致\(\text{lcp}\)不同. 但因为不同的\(\text{lca}\)的个数和入度加出度是同一个规模的.

我们考虑直接建出关于这些关键点的虚树, 然后在虚树的\(\text{dfs}\)序上用线段树优化建边就好了.

具体的:我们要维护两颗线段树一颗入线段树, 一颗出线段树. 入线段树维护能到这个点的边上的\(\text{Trie}\)树上的点集, 出线段树同理.

入线段树上每个叶子节点直接连向原图中的点边权为原图中的边权. 对于出线段树上的每个节点, 由原图中的点向其连边, 边权为\(\text{0}\).

对于虚树上的一对点\(\text{(u,v)}\)它俩儿的\(\text{lca}\)要么等于\(\text{u,v}\)其中之一,要等于别的点.所以剩下来有两种情况:

我们枚举一个虚树上的点\(\text{x}\).

  1. 等于其中之一,我们直接把\(\text{x}\)在入线段树上所对应的叶子节点连向出线段树中\(\text{x}\)的子树所对应的区间或者入线段树中\(\text{x}\)的子树对应的区间连向出线段树中\(\text{x}\)所对应的叶子节点.
  2. 否则,我们枚举一个\(\text{x}\)的一个子树, 将这个子树向\(\text{x}\)的前缀子树和后缀子树分别连边, 连边方法同\(\text{1}\).

连完边后直接跑一遍\(\text{Dijkstra}\)就好了.

\(\text{SDOIR2}\)的题目质量还是一如既往的高啊!就是毒瘤正解很妙妙啊.

代码:

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
217
218
219
220
221
222
223
224
225
226
227
228
229
230
/*
* 4912.cpp
* This file is part of BZOJ4912
*
* Copyright (C) 2019 - ViXbob
*
* BZOJ4912 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.
*
* BZOJ4912 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 BZOJ4912. 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 pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

typedef long long ll;

using namespace std;

const int maxn = 1e5 + 5;
const int LOG = 20;
const int inf = 0x3f3f3f3f;

int T, n, m, k, tot, bel[maxn];
int dep[maxn], fa[maxn][20], dfn[maxn], pos[maxn], point[maxn];
vector<int> E[maxn], H[maxn];
vector<pair<pair<int, int>, pair<int, int> > > Out[maxn], In[maxn];
vector<pair<int, int> > G[maxn * LOG], nid[maxn];

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;
}

inline void Debug(int x, int y, int w) { return; cerr << "SEG add : " << x << " -> " << y << ", w = " << w << endl; }
inline void RDebug(int x, int y) { return; cerr << "Tree add : " << x << " -> " << y << endl; }

inline void dfs(int x) { // dfs for trie
dfn[x] = ++dfn[0]; pos[x] = dfn[0];
for(int i = 1; dep[x] >> i; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
for(auto v : E[x]) {
if(v == fa[x][0]) continue;
dep[v] = dep[x] + 1;
fa[v][0] = x; dfs(v);
}
}

inline int Jump(int x, int d) {
for(int i = 0; d; d >>= 1, i++) if(d & 1) x = fa[x][i];
return x;
}

inline int LCA(int x, int y) {
if(dep[x] < dep[y]) swap(x, y);
x = Jump(x, dep[x] - dep[y]);
if(x == y) return x;
for(int i = 19; ~i; i--) if(fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i];
return fa[x][0];
}

int st[maxn], top, ndfn[maxn], npos[maxn], is[maxn], nfa[maxn], ed[maxn], ndep[maxn], vis[maxn];
vector<int> tmp, p;

inline void add(int x, int y, vector<int> *G) { G[x].pb(y); G[y].pb(x); RDebug(x, y); }

inline void push(int x) {
tmp.pb(x);
if(top <= 0) return (void)(st[++top] = x);
int lca = LCA(x, st[top]);
if(lca == st[top]) return (void)(st[++top] = x);
while(top > 1 && pos[st[top - 1]] >= pos[lca]) add(st[top], st[top - 1], H), top--;
if(lca != st[top]) add(lca, st[top], H), st[top] = lca, tmp.pb(lca);
return (void)(st[++top] = x);
}

inline void redfs(int x) {
ndfn[++ndfn[0]] = x; npos[x] = ndfn[0];
ed[x] = ndfn[0];
for(auto v : H[x]) {
if(v == nfa[x]) continue;
nfa[v] = x; ndep[v] = ndep[x] + 1;
redfs(v); ed[x] = ed[v];
}
}

struct SEG {
#define ls p << 1
#define rs p << 1 | 1
#define mid (l + r >> 1)
int id[maxn << 2], rid[maxn];
inline void Build(int l, int r, int p, bool type) {
id[p] = ++tot;
if(l == r) {
for(auto v : nid[ndfn[r]])
type ? (G[id[p]].pb(v), Debug(id[p], v.first, v.second)) : (G[v.first].pb(mp(id[p], 0)), Debug(v.first, id[p], 0));
return (void)(rid[r] = id[p]);
}
Build(l, mid, ls, type); Build(mid + 1, r, rs, type);
if(type) G[id[p]].pb(mp(id[ls], 0)), G[id[p]].pb(mp(id[rs], 0));
else G[id[ls]].pb(mp(id[p], 0)), G[id[rs]].pb(mp(id[p], 0));
}
inline void Link(int l, int r, int ql, int qr, int p, int u, int w, bool type) {
if(ql > qr) return;
if(l == ql && r == qr) return (void)(type ? (G[id[p]].pb(mp(u, w)), Debug(id[p], u, w)) : (G[u].pb(mp(id[p], w)), Debug(u, id[p], w)));
if(qr <= mid) Link(l, mid, ql, qr, ls, u, w, type);
else if(ql > mid) Link(mid + 1, r, ql, qr, rs, u, w, type);
else Link(l, mid, ql, mid, ls, u, w, type), Link(mid + 1, r, mid + 1, qr, rs, u, w, type);
}
#undef ls
#undef rs
#undef mid
} Tin, Tout;

int dis[maxn * LOG], ans[maxn];

inline void Dijkstra() {
priority_queue<pair<int, int> > q;
fill(dis, dis + tot + 1, 2 * inf);
fill(ans, ans + n + 1, 2 * inf);
q.push(mp(dis[1] = 0, 1));
while(q.size()) {
int u = q.top().second, now = q.top().first; q.pop();
if(u <= m + 1) ans[bel[u]] = min(ans[bel[u]], dis[u]);
if(dis[u] != -now) continue;
for(auto v : G[u]) {
if(dis[v.first] > dis[u] + v.second) {
dis[v.first] = dis[u] + v.second;
q.push(mp(-dis[v.first], v.first));
}
}
}
rep(i, 2, n) printf("%d\n", ans[i]);
rep(i, 1, tot) G[i].clear();
}

inline void init() {
tot = 0;
memset(fa, 0, sizeof(fa));
memset(dfn, 0, sizeof(dfn));
memset(point, 0, sizeof(point));
rep(i, 0, n) Out[i].clear(), In[i].clear();
rep(i, 0, k) E[i].clear();
}

int main() {
// freopen("hack19.in", "r", stdin);
// freopen("my.out", "w", stdout);
// freopen("debug.log", "w", stderr);
T = read();
while(T--) {
n = read(); m = read(); k = read(); init();
In[1].pb(mp(mp(0, tot = 1), mp(0, 1))); bel[1] = 1;
rep(i, 1, m) {
int x = read(), y = read(), w = read(), c = read();
Out[x].pb(mp(mp(y, ++tot), mp(w, c)));
In[y].pb(mp(mp(x, tot), mp(w, c)));
bel[tot] = y;
}
rep(i, 1, k - 1) {
int x = read(), y = read(), w = read();
E[x].pb(y); E[y].pb(x);
}
dfs(1);
rep(i, 1, n) {
tmp.clear(); p.clear(); top = 0;
for(auto v : In[i]) if(!vis[v.second.second])
p.pb(v.second.second), vis[v.second.second] = -1;
for(auto v : Out[i]) if(!vis[v.second.second])
p.pb(v.second.second), vis[v.second.second] = 1;
sort(p.begin(), p.end(), [](int x, int y) -> bool { return pos[x] < pos[y]; });
for(auto v : p) push(v);
while(top > 1) add(st[top], st[top - 1], H), top--;
sort(tmp.begin(), tmp.end(), [](int x, int y) -> bool { return pos[x] < pos[y]; });
ndfn[0] = 0; ndep[*tmp.begin()] = 0; redfs(*tmp.begin());
for(auto v : In[i]) nid[v.second.second].pb(mp(v.first.second, v.second.first));
Tin.Build(1, ndfn[0], 1, 0);
for(auto v : In[i]) nid[v.second.second].clear();
for(auto v : Out[i]) nid[v.second.second].pb(mp(v.first.second, v.second.first));
Tout.Build(1, ndfn[0], 1, 1);
for(auto v : Out[i]) nid[v.second.second].clear();
for(auto u : tmp) {
Tout.Link(1, ndfn[0], npos[u], ed[u], 1, Tin.rid[npos[u]], dep[u], 0);
Tin.Link(1, ndfn[0], npos[u], ed[u], 1, Tout.rid[npos[u]], dep[u], 1);
if(SIZE(H[u]) - (u != *tmp.begin()) >= 2) {
for(auto v : H[u]) {
tot++;
Tin.Link(1, ndfn[0], npos[v], ed[v], 1, tot, dep[u], 1);
Tout.Link(1, ndfn[0], npos[u] + 1, npos[v] - 1, 1, tot, 0, 0);
Tout.Link(1, ndfn[0], ed[v] + 1, ed[u], 1, tot, 0, 0);
tot++;
Tout.Link(1, ndfn[0], npos[v], ed[v], 1, tot, dep[u], 0);
Tin.Link(1, ndfn[0], npos[u] + 1, npos[v] - 1, 1, tot, 0, 1);
Tin.Link(1, ndfn[0], ed[v] + 1, ed[u], 1, tot, 0, 1);
}
}
}
for(auto u : tmp) ndfn[u] = npos[u] = nfa[u] = ed[u] = ndep[u] = vis[u] = 0, H[u].clear();
} Dijkstra();
}
return 0;
}
/*
*/

残缺的字符串

定义两个字符串\(A,B\)的相似程度为: \[ \sum_{i=0}^{L-1}(A_i-B_i)^2A_iB_i \]

然后直接将\(B\)翻转一下就是一个卷积的形式, 做完\(FFT\)后系数为\(0\)的位置就是匹配位置.

代码:

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
// luogu-judger-enable-o2
/*
* A.cpp
* This file is part of NOI_AC_2019_04_24_A
*
* Copyright (C) 2019 - ViXbob
*
* NOI_AC_2019_04_24_A 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.
*
* NOI_AC_2019_04_24_A 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 NOI_AC_2019_04_24_A. If not, see <http://www.gnu.org/licenses/>.
*/

// Begin at 2019-04-24 08:18:54 - ViXbob

/**
* 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())

using namespace std;

const int maxn = 3e5 + 5;
const int maxm = maxn << 2;
const double pi = acos(-1.0);

int n, m, a[maxn], b[maxn];
char S[maxn], t[maxn];

struct Complex {
double x, y;
Complex(double a = 0, double b = 0) { x = a; y = b; }
Complex operator + (const Complex &t) const { return Complex(x + t.x, y + t.y); }
Complex operator - (const Complex &t) const { return Complex(x - t.x, y - t.y); }
Complex operator * (const Complex &t) const { return Complex(x * t.x - y * t.y, x * t.y + y * t.x); }
Complex operator / (const int &t) const { return Complex(x / t, y / t); }
Complex operator * (const int &t) const { return Complex(x * t, y * t); }
} tmp[maxm];

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;
}

namespace FFT {
Complex E[maxm], H[maxm];
int rev[maxm], s, l;

inline void init(int n) {
l = 1; s = 2;
while(s <= n) s <<= 1, l++;
rep(i, 0, s - 1) rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
memset(E, 0, sizeof(Complex) * (s + 5));
memset(H, 0, sizeof(Complex) * (s + 5));
}

inline void dft(Complex *a, int n, int type) {
rep(i, 0, n - 1) if(i < rev[i]) swap(a[i], a[rev[i]]);
for(int i = 1; i < n; i <<= 1) {
Complex Wn(cos(pi / i), type * sin(pi / i));
for(int j = 0; j < n; j += (i << 1)) {
Complex w(1, 0);
for(int k = 0; k < i; k++, w = w * Wn) {
Complex A1 = a[j + k], A2 = w * a[j + k + i];
a[j + k] = A1 + A2; a[j + k + i] = A1 - A2;
}
}
}
}
}

using namespace FFT;

int main() {
scanf("%d%d%s%s", &n, &m, S, t);
// n = read() + 1; m = read() + 1;
init(n + m - 2);
rep(i, 0, n - 1) a[i] = S[n - 1 - i] == '*' ? 0 : S[n - 1 - i] - 'a' + 1;
rep(i, 0, m - 1) b[i] = t[i] == '*' ? 0 : t[i] - 'a' + 1;
// rep(i, 0, n - 1) cerr << "a[" << i << "] = " << a[i] << endl;
// rep(i, 0, m - 1) cerr << "b[" << i << "] = " << b[i] << endl;

rep(i, 0, n - 1) E[i] = Complex(a[i] * a[i] * a[i], 0);
rep(i, 0, m - 1) H[i] = Complex(b[i]);
dft(E, s, 1); dft(H, s, 1);
rep(i, 0, s - 1) tmp[i] = E[i] * H[i];

rep(i, 0, s - 1) E[i] = H[i] = Complex();
rep(i, 0, n - 1) E[i] = Complex(a[i] * a[i], 0);
rep(i, 0, m - 1) H[i] = Complex(b[i] * b[i], 0);
dft(E, s, 1); dft(H, s, 1);
rep(i, 0, s - 1) tmp[i] = tmp[i] - E[i] * H[i] * 2;

rep(i, 0, s - 1) E[i] = H[i] = Complex();
rep(i, 0, n - 1) E[i] = Complex(a[i], 0);
rep(i, 0, m - 1) H[i] = Complex(b[i] * b[i] * b[i], 0);
dft(E, s, 1); dft(H, s, 1);
rep(i, 0, s - 1) tmp[i] = tmp[i] + E[i] * H[i];

dft(tmp, s, -1); queue<int> q;
rep(i, 0, s - 1) tmp[i] = tmp[i] / s;
rep(i, n - 1, m - 1) if((int)(tmp[i].x + 0.5) == 0) q.push(i - n + 2);
cout << q.size() << endl;
while(q.size()) printf("%d ", q.front()), q.pop();
return 0;
}

循环之美

Link

国王饮水记

Link

期末考试

Link

相逢是问候

Link

组合数问题

Link

摧毁「树状图」

Link

分手是祝愿

Link

寿司餐厅

Link

公约数数列

首先分块对于每个块中的每个元素,不用记其整个序列的前缀\(\gcd\)只用记录在这个块中的前缀\(\gcd\)就好了.异或值同理.(否则无法快速修改)

并且我们知道对于一个序列的不同的前缀\(\gcd\)个数只有\(\log\)个.所以如果同一个块中的第一个元素和最后一个元素的前缀\(\gcd\)相同的话我们可以直接查询(用\(\text{unordered_map}\)维护一下),否则暴力扫这个块.这样的话我们最多只会扫\(\log\)个块.

复杂度\(O(n\sqrt{n}\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
/*
* 4028.cpp
* This file is part of BZOJ_4028
*
* Copyright (C) 2019 - ViXbob
*
* BZOJ_4028 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.
*
* BZOJ_4028 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 BZOJ_4028. 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 st(x) (ed[x - 1] + 1)

typedef unsigned long long ull;
typedef long long ll;

using namespace std;

const int maxn = 1e5 + 5;
const int P = 1e5 + 3;

int n, a[maxn], q, B, be[maxn], ed[maxn], gcd[maxn], Xor[maxn];
unordered_map<int, int> mp[360];
char opt[10];

inline ll read() {
char ch = getchar(); ll 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;
}

inline void ReBuild(int id) {
mp[id].clear();
gcd[st(id)] = a[st(id)]; Xor[st(id)] = a[st(id)]; mp[id][Xor[st(id)]] = st(id);
rep(i, st(id) + 1, ed[id]) gcd[i] = __gcd(gcd[i - 1], a[i]);
rep(i, st(id) + 1, ed[id]) {
Xor[i] = Xor[i - 1] ^ a[i];
if(!mp[id].count(Xor[i])) mp[id][Xor[i]] = i;
}
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read();
rep(i, 1, n) a[i] = read();
q = read(); B = sqrt(n);
rep(i, 1, n) be[i] = (i - 1) / B + 1, ed[be[i]] = i;
rep(i, 1, be[n]) ReBuild(i);
while(q--) {
scanf("%s", opt + 1); ll x = read();
if(opt[1] == 'M') x++, a[x] = read(), ReBuild(be[x]);
else {
int lstgcd = 0, lstxor = 0, ans = -1;
rep(i, 1, be[n]) {
int Begin = __gcd(lstgcd, gcd[st(i)]), End = __gcd(lstgcd, gcd[ed[i]]);
if(Begin == End) {
if(x % End == 0) if(mp[i].count((x / End) ^ lstxor))
ans = mp[i][(x / End) ^ lstxor];
lstgcd = __gcd(lstgcd, gcd[ed[i]]); lstxor ^= Xor[ed[i]];
} else {
rep(j, st(i), ed[i]) {
lstgcd = __gcd(lstgcd, a[j]);
lstxor ^= a[j];
if(1ll * lstgcd * lstxor == x) { ans = j; break; }
}
}
if(~ans) break;
}
if(~ans) printf("%d\n", ans - 1); else puts("no");
}
}
return 0;
}
/*
*/

单旋

HNOI2017题解.

影魔

HNOI2017题解.

礼物

HNOI2017题解.

大佬

HNOI2017题解.

抛硬币

HNOI2017题解.

序列计数

先考虑不要求有质数的怎么做,设\(f[i][j]\)表示考虑了前\(i\)个数,和在膜\(p\)意义下为\(j\)的方案数,则有转移: \[ f[i][j] =\sum_{k=0}^{p-1}f[i-1][(j-k+p)\bmod p]\times c[k] \] \(c[i]\)表示数集中在膜\(p\)意义下为\(i\)的数的个数.

显然可以矩阵快速幂优化.

然后我们容斥一下,用没有限制的方案数减去全都是合数的方案数即是至少包含一个质数的方案数.

复杂度\(O(p^3\log n)\).这玩意儿显然也是个卷积的形式\(\text{MTT}\)搞搞复杂度是\(O(p \log p \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
/*
* 4818.cpp
* This file is part of 4818
*
* Copyright (C) 2019 - ViXbob
*
* 4818 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.
*
* 4818 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 4818. 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())

typedef long long ll;

using namespace std;

const int maxn = 2e7 + 5;
const int P = 20170408;

int n, m, p, prime[maxn / 10], cnt, con[105], icon[105];
bool vis[maxn];

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;
}

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 void PreSolve(int n) {
vis[1] = 1; con[1]++; icon[1]++;
for(int i = 2, lst = 1; i <= n; i++) {
lst = (lst + 1 < p ? lst + 1 : lst + 1 - p); con[lst]++;
vis[i] ? icon[lst]++ : prime[++cnt] = i;
for(int j = 1; j <= cnt && 1ll * prime[j] * i <= n; j++) {
vis[prime[j] * i] = 1;
if(i % prime[j] == 0) break;
}
}
}

struct Matrix {
int H, W;
vector<vector<int> > mat;
Matrix(int a = 0, int b = 0) {
H = a; W = b;
mat.resize(H);
for(auto &v : mat) v.resize(W);
}
vector<int> &operator [] (int i) { return mat[i]; }
Matrix operator * (const Matrix &t) const {
Matrix rnt(H, t.W);
rep(i, 0, H - 1) rep(j, 0, t.W - 1) rep(k, 0, W - 1)
rnt[i][j] = (rnt[i][j] + 1ll * mat[i][k] * t.mat[k][j] % P) % P;
return rnt;
}
Matrix operator ^ (const int k) const {
Matrix tmp(H, W), x = (*this);
rep(i, 0, H - 1) tmp[i][i] = 1;
for(int i = k; i; i >>= 1, x = x * x) if(i & 1) tmp = tmp * x;
return tmp;
}
} A, B;

Matrix Solve(int *con, int n) {
Matrix T(p, p), rnt(1, p);
rep(j, 0, p - 1) rep(i, 0, p - 1) T[i][j] = con[(j - i + p) % p];
rnt[0][0] = 1;
T = T ^ n;
return rnt * T;
}

int main() {
// freopen("1.in", "r", stdin);
n = read(); m = read(); p = read();
PreSolve(m);
A = Solve(con, n); B = Solve(icon, n);
cout << (A[0][0] - B[0][0] + P) % P << endl;
return 0;
}

新生舞会

二分答案后费用流\(check\)即可.(怎么打都行)

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
/*
* 4819.cpp
* This file is part of 4819
*
* Copyright (C) 2019 - ViXbob
*
* 4819 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.
*
* 4819 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 4819. 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)

typedef long long ll;

using namespace std;

const int maxn = 2e2 + 15;
const int maxm = maxn * maxn;
const int P = 20170408;
const double eps = 1e-8;
const int inf = 0x3f3f3f3f;

int n, a[maxn][maxn], b[maxn][maxn], suma, sumb;

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;
}

namespace NetFlow {
int head[maxn], cnt = 1;
struct Graph {
int fr, to, nt, flow, cap; double w;
Graph(int a = 0, int b = 0, int c = 0, int d = 0, int e = 0, double f = 0) {
fr = a; to = b; nt = c; flow = d; cap = e; w = f;
}
} e[maxm << 2];

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

int MaxFlow, S, T, vis[maxn];
double MinCost, delta, dis[maxn];

inline void clear() {
cnt = 1; MaxFlow = MinCost = delta = 0;
memset(head, 0, sizeof(head));
}

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

inline bool SPFA() {
static bool inq[maxn];
queue<int> q;
memset(inq, 0, sizeof(inq));
memset(dis, 0x43, sizeof(dis));
dis[T] = 0; q.push(T);
while(!q.empty()) {
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].flow, c = e[i ^ 1].cap;
double w = e[i ^ 1].w;
if(dis[v] > dis[u] + w && f < c) {
dis[v] = dis[u] + w;
if(!inq[v]) q.push(v), inq[v] = 1;
}
}
} return dis[S] != dis[0];
}

inline bool Dijkstra() {
priority_queue<pair<double, int> > q;
memset(dis, 0x43, sizeof(dis));
q.push(mp(dis[T] = 0, T));
while(!q.empty()) {
int u = q.top().second; double now = -q.top().first; q.pop();
if(now != dis[u]) continue;
for(int i = head[u]; i; i = e[i].nt) {
int v = e[i].to, f = e[i ^ 1].flow, c = e[i ^ 1].cap;
double w = e[i ^ 1].w;
if(dis[v] > dis[u] + w && f < c) {
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;
int res = flow; vis[x] = 1;
for(int i = head[x]; i; i = e[i].nt) {
int v = e[i].to, f = e[i].flow, c = e[i].cap;
double w = e[i].w;
if(fabs(w) <= eps && f < c && !vis[v]) {
int tmp = dfs(v, min(res, c - f));
e[i].flow += tmp; e[i ^ 1].flow -= tmp;
res -= tmp;
}
} return flow - res;
}

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

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

inline bool check(double mid) {
NetFlow :: clear();
NetFlow :: S = 2 * n + 1; NetFlow :: T = NetFlow :: S + 1;
rep(i, 1, n) NetFlow :: add(NetFlow :: S, i, 1, 0);
rep(i, 1, n) NetFlow :: add(i + n, NetFlow :: T, 1, 0);
rep(i, 1, n) rep(j, 1, n) NetFlow :: add(i, j + n, 1, b[i][j] * mid - a[i][j]);
NetFlow :: PrimalDual();
return NetFlow :: MinCost <= eps;
}

inline double Biniry(double l, double r) {
double mid, rnt = 0;
while(fabs(r - l) > eps) {
mid = (l + r) / 2;
if(check(mid)) l = mid + eps, rnt = mid;
else r = mid - eps;
} return rnt;
}

int main() {
// freopen("1.in", "r", stdin);
n = read();
priority_queue<int> q;
rep(i, 1, n) rep(j, 1, n) a[i][j] = read(), q.push(a[i][j]);
int x = n; while(x--) suma += q.top(), q.pop();
while(q.size()) q.pop();
rep(i, 1, n) rep(j, 1, n) b[i][j] = read(), q.push(-b[i][j]);
x = n; while(x--) sumb -= q.top(), q.pop();
// cerr << suma << " " << sumb << endl;
printf("%.6lf\n", Biniry(eps, (double)(suma) / (sumb * 1.0)));
return 0;
}

硬币游戏

妙妙题,见Link

相关分析

沙茶线段树题???

直接把式子拆开然后分别维护一下就好了.

注意如果求:\(\sum_{i=1}^ni^2=\frac{n\times (n+1)\times (2n+1)}{6}或者\sum_{i=1}^ni=\frac{n \times (n+1)}{2}\)用的是\(\text{define}\)要乘上\(\text{1ll}\), 还要打括号.调了一年,爆哭/(ㄒoㄒ)/~~例如:

1
2
#define getd(x) (1ll * (1 + (x)) * (x) / 2)
#define getdd(x) (1ll * (x) * ((x) + 1) * (2 * (x) + 1) / 6)

字符串

二分答案很妙啊.

首先我们知道在反串的\(\text{parent}\)树上两个反串前缀的状态的\(\text{lca}\)即是原两个后缀的的\(\text{lcp}\)所在的状态.所以下文考虑的均是反串,并且询问的左右端点也翻转了.

然后我们二分\(\text{lcp}\)的长度\(m\),通过倍增定位\(\text{lcp}\)的状态\(x\),然后就变成了查询\(x\)的子树中有没有存在的点.

然后这个东西可以用主席树来解决.

具体的我们每次向主席树上插入一个前缀状态时都新开一个版本,然后查询包含\([a+mid-1,b]\)这个区间的前缀的线段树上的\(x\)的子树中是否有点.

PS:叙述有点不清楚,建议看代码.

复杂度\(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
/*
* 4556.cpp
* This file is part of 4556
*
* Copyright (C) 2019 - ViXbob
*
* 4556 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.
*
* 4556 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 4556. 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 id(x, y) ((x - 1) * m + y)
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)

typedef long long ll;

using namespace std;

const int maxn = 2e5 + 5;
const int inf = 0x3f3f3f3f;
const int LOG = 35;

int n, q;
char s[maxn];

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;
}

namespace FSEG {
#define mid (l + r >> 1)
#define Ls(x) (t[x].ls)
#define Rs(x) (t[x].rs)
int root[maxn], tot;
struct {
int ls, rs, size;
} t[maxn * LOG];

inline void insert(int l, int r, int pos, int u, int &p) {
p = ++tot; t[p] = t[u]; t[p].size++;
if(l == r) return;
if(pos <= mid) insert(l, mid, pos, Ls(u), Ls(p));
else insert(mid + 1, r, pos, Rs(u), Rs(p));
}

inline int query(int l, int r, int ql, int qr, int u, int p) {
if(!p) return 0;
if(l == ql && r == qr) return t[p].size - t[u].size;
if(qr <= mid) return query(l, mid, ql, qr, Ls(u), Ls(p));
else if(ql > mid) return query(mid + 1, r, ql, qr, Rs(u), Rs(p));
else return query(l, mid, ql, mid, Ls(u), Ls(p)) + query(mid + 1, r, mid + 1, qr, Rs(u), Rs(p));
}
#undef mid
#undef Ls
#undef Rs
}

using namespace FSEG;

namespace SAM {
int lst = 1, cnt = 1, fa[maxn][20], ch[maxn][26], maxlen[maxn], size[maxn], pos[maxn];
int dfn[maxn], ed[maxn], coc;
vector<int> G[maxn];

inline void Extend(int c, int n) {
int p = lst, cur = ++cnt; maxlen[cur] = maxlen[p] + 1;
size[cur] = 1;
for( ; p && !ch[p][c]; p = fa[p][0]) ch[p][c] = cur;
if(!p) fa[cur][0] = 1;
else {
int q = ch[p][c];
if(maxlen[q] == maxlen[p] + 1) fa[cur][0] = q;
else {
int clone = ++cnt;
memcpy(ch[clone], ch[q], sizeof(ch[q]));
fa[clone][0] = fa[q][0]; fa[q][0] = fa[cur][0] = clone;
maxlen[clone] = maxlen[p] + 1;
for( ; p && ch[p][c] == q; p = fa[p][0]) ch[p][c] = clone;
}
} lst = pos[n] = cur;
}

inline void dfs(int x) {
dfn[x] = ed[x] = ++coc;
for(auto v : G[x]) dfs(v), ed[x] = ed[v];
}

inline void PreSolve() {
rep(j, 1, 19) rep(i, 1, cnt) fa[i][j] = fa[fa[i][j - 1]][j - 1];
rep(i, 2, cnt) G[fa[i][0]].pb(i);
dfs(1);
rep(i, 1, n) insert(1, coc, dfn[pos[i]], root[i - 1], root[i]);
}

inline int DefineL(int x, int len) {
for(int i = 19; ~i; --i) if(maxlen[fa[x][i]] >= len) x = fa[x][i];
return x;
}
}

using namespace SAM;

inline int Biniry(int l, int r, int L, int R, int rnt = 0) {
int Vl = 1, Vr = min(r - l + 1, R - L + 1), mid;
while(Vl <= Vr) {
mid = Vl + Vr >> 1;
// cerr << "l = " << Vl << ", r = " << Vr << endl;
// cerr << "State = " << pos[R] << endl;
// cerr << fa[pos[R]][0] << endl;
int S = DefineL(pos[R], mid);
// cerr << "State = " << S << endl;
int tmp = query(1, coc, dfn[S], ed[S], root[l + mid - 2], root[r]);
(tmp > 0) ? (Vl = mid + 1, rnt = mid) : Vr = mid - 1;
} return rnt;
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); q = read();
scanf("%s", s + 1);
dep(i, n, 1) Extend(s[i] - 'a', n - i + 1);
// cerr << endl;
PreSolve();
while(q--) {
int l = read(), r = read(), L = read(), R = read();
l = n - l + 1; r = n - r + 1; L = n - L + 1; R = n - R + 1;
swap(l, r); swap(L, R);
printf("%d\n", Biniry(l, r, L, R));
}
return 0;
}

甲苯先生的字符串

TJOI2019题解

甲苯先生的滚榜

TJOI2019题解

唱、跳、rap 和篮球

TJOI2019题解

大中锋的游乐场

TJOI2019题解

甲苯先生和大中锋的字符串

TJOI2019题解

甲苯先生的线段树

TJOI2019题解

特技飞行

GXOI2019题解

逼死强迫症

GXOI2019题解

旅行者

GXOI2019题解

旧词

GXOI2019题解

礼物

SNOI2017题解

一个简单的询问

SNOI2017题解

炸弹

SNOI2017题解

英雄联盟

SNOI2017题解

遗失的答案

SNOI2017题解

字符串

SNOI2019题解

数论

SNOI2019题解

通信

SNOI2019题解