HNOI2017

单旋

单独考虑每个操作的对其他元素的深度的影响:

  1. 插入元素\(x\)一定是其前驱的右儿子或者后继的左儿子(二者一定只有一个是满足条件).
  2. 最小值的深度变为\(1\), 剩余的元素除了最小值的右子树的元素深度不变外,其余深度加一.
  3. 最大值的深度变为\(1\), 剩余的元素除了最大值的左子树的元素深度不变外,其余深度加一.
  4. 除了最小值的右子树的元素深度减一外,其余深度不变.
  5. 除了最小值的左子树的元素深度减一外,其余深度不变.

然后我们用\(\text{Splay}\)维护每个节点的深度, 用数组维护\(\text{Spaly}\)的形态.

无论是\(\text{while}\)模拟递归还是递归,都要下传\(\text{tag}\).

无论是\(\text{while}\)模拟递归还是递归,都要下传\(\text{tag}\).

无论是\(\text{while}\)模拟递归还是递归,都要下传\(\text{tag}\).

重要的事情说三遍.我才不会告诉你我因为这个调了一年呢!

代码:

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
/*
* 4825.cpp
* This file is part of BZOJ_4825
*
* Copyright (C) 2019 - ViXbob
*
* BZOJ_4825 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_4825 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_4825. 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 id(x, y) (1000 + (x - 1) * n + y)

typedef unsigned long long ull;
typedef long long ll;

using namespace std;

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

int m, ch[maxn][2], fa[maxn], Rt, cnt;

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 Splay {
#define who(x) (x == t[t[x].fa].ch[1])
int root;
struct Node {
int ch[2], w, fa, dep, tag;
inline void clear() { ch[0] = ch[1] = w = fa = dep = tag = 0; }
} t[maxn];

inline void pushtag(int p, int x) {
if(!p) return;
t[p].tag += x; t[p].dep += x;
}

inline void pushdown(int p) {
if(t[p].tag) {
pushtag(t[p].ch[0], t[p].tag);
pushtag(t[p].ch[1], t[p].tag);
t[p].tag = 0;
}
}

inline void pushall(int x) {
if(t[x].fa) pushall(t[x].fa); pushdown(x);
}

inline void rotate(int x) {
int y = t[x].fa, z = t[y].fa, w = !who(x);
t[z].ch[who(y)] = x; t[x].fa = z;
t[y].ch[w ^ 1] = t[x].ch[w]; t[t[x].ch[w]].fa = y;
t[x].ch[w] = y; t[y].fa = x;
}

inline void splay(int x, int goal) {
pushall(x);
while(t[x].fa != goal) {
int y = t[x].fa, z = t[y].fa;
if(z != goal) rotate(who(x) ^ who(y) ? x : y);
rotate(x);
}
root = goal ? root : x;
}

inline int findx(int x) {
int o = root;
while(t[o].w != x) pushdown(o), o = t[o].ch[t[o].w < x];
splay(o, 0); return o;
}

inline void insert(int x, int id, int w) {
int o = root;
while(t[o].ch[t[o].w < x]) pushdown(o), o = t[o].ch[t[o].w < x];
t[o].ch[t[o].w < x] = id;
t[id].w = x; t[id].fa = o; t[id].dep = w;
splay(id, 0);
}

inline int pre(int x, int rnt = -inf, int id = 0) {
int o = root;
while(o) {
pushdown(o);
if(t[o].w < x) {
if(t[o].w > rnt) rnt = t[o].w, id = o;
o = t[o].ch[1];
} else o = t[o].ch[0];
} return id;
}

inline int suc(int x, int rnt = inf, int id = 0) {
int o = root;
while(o) {
pushdown(o);
if(t[o].w > x) {
if(t[o].w < rnt) rnt = t[o].w, id = o;
o = t[o].ch[0];
} else o = t[o].ch[1];
} return id;
}
#undef who
}

using namespace Splay;

inline int Insert(int x) {
++cnt; int w = 0;
int Pre = pre(x), Suc = suc(x);
if(!Pre && !Suc) Rt = cnt, w = 1;
else if(!ch[Pre][1] && Pre) ch[Pre][1] = cnt, fa[cnt] = Pre, w = t[Pre].dep + 1;
else ch[Suc][0] = cnt, fa[cnt] = Suc, w = t[Suc].dep + 1;
insert(x, cnt, w); return w;
}

inline int MinSpaly() {
int x = suc(0), y = fa[x], w = 0;
if(x == Rt) return 1;
splay(y, 0); splay(x, y); w = t[x].dep;
t[y].dep++; pushtag(t[y].ch[1], 1);
t[x].dep = 1;
ch[y][0] = ch[x][1]; fa[ch[x][1]] = y;
fa[Rt] = x; ch[x][1] = Rt;
Rt = x; fa[x] = 0;
return w;
}

inline int MaxSpaly() {
int x = pre(inf), y = fa[x], w = 0;
if(x == Rt) return 1;
splay(y, 0); splay(x, y); w = t[x].dep;
t[y].dep++; pushtag(t[y].ch[0], 1);
t[x].dep = 1;
ch[y][1] = ch[x][0]; fa[ch[x][0]] = y;
fa[Rt] = x; ch[x][0] = Rt;
Rt = x; fa[x] = 0;
return w;
}

inline int MinDelete() {
int x = suc(0), y = fa[x], w = 0;
if(x == Rt) {
fa[ch[x][1]] = 0; Rt = ch[x][1];
splay(x, 0); root = t[x].ch[1]; t[t[x].ch[1]].fa = 0;
t[x].clear();
pushtag(root, -1); return 1;
}
splay(y, 0); splay(x, y);
pushtag(t[x].ch[1], -1);
ch[y][0] = ch[x][1]; fa[ch[x][1]] = y;
splay(x, 0);
root = t[x].ch[1]; t[t[x].ch[1]].fa = 0;
w = t[x].dep; t[x].clear();
return w;
}

inline int MaxDelete() {
int x = pre(inf), y = fa[x], w = 0;
if(x == Rt) {
fa[ch[x][0]] = 0; Rt = ch[x][0];
splay(x, 0); root = t[x].ch[0]; t[t[x].ch[0]].fa = 0;
t[x].clear();
pushtag(root, -1); return 1;
}
splay(y, 0); splay(x, y);
pushtag(t[x].ch[0], -1);
ch[y][1] = ch[x][0]; fa[ch[x][0]] = y;
splay(x, 0);
root = t[x].ch[0]; t[t[x].ch[0]].fa = 0;
w = t[x].dep; t[x].clear();
return w;
}

int main() {
// freopen("4.in", "r", stdin);
// freopen("my.out", "w", stdout);
m = read(); int con = 0;
while(m--) {
int opt = read();
if(opt == 1) printf("%d\n", Insert(read()));
else if(opt == 2) printf("%d\n", MinSpaly());
else if(opt == 3) printf("%d\n", MaxSpaly());
else if(opt == 4) printf("%d\n", MinDelete());
else printf("%d\n", MaxDelete());
}
return 0;
}
/*
8
1 2
1 1
1 4
1 3
1 5
3
1 6
2
*/

影魔

一个二元组\((i, j), i < j\)如果满足\(a[i], a[j]\)是区间\([i,j]\)的最大值和次大值这个二元组的贡献为\(p_1\), 否则如果\(\max_{i < k < j}\{a_k\} \in (\min(a_i,a_j),\max(a_i,a_j))\)\(p_2\)的贡献.

考虑到一个二元组的贡献取决于\(a_i, a_j, \max_{i < k < j}\{a_k\}\), 我们可以考虑每一个\(\max_{i < k < j}\{a_k\}\)的贡献.

首先我们可以对每一个\(a_i\)求出来右边第一个大于它的数的位置\(r_i\)和左边第一个大于它的数的位置\(l_i\).

可知对于一个最大值\(a_i\):

左端点等于\(l_i\), 右端点等于\(i\)或者左端点等于\(i\), 右端点等于\(r_i\)的二元组都有\(p_1\)的贡献.

左端点等于\(l_i\),右端点属于\((i,r_i]\)或者左端点属于\([l_i,i)\),右端点等于\(r_i\)的二元组有\(p_2\)的贡献.

注意到对于\(l_i=i-1\)或者\(r_i = i+1\)\(p_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
/*
* 4825.cpp
* This file is part of BZOJ_4825
*
* Copyright (C) 2019 - ViXbob
*
* BZOJ_4825 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_4825 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_4825. 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 id(x, y) (1000 + (x - 1) * n + y)

typedef unsigned long long ull;
typedef long long ll;

using namespace std;

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

int n, m, p1, p2, a[maxn];
pair<pair<int, int>, int> q[maxn];
vector<pair<int, int> > Q[maxn], M[maxn];
ll ans[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;
}

struct SEG {
#define ls p << 1
#define rs p << 1 | 1
#define mid (l + r >> 1)
ll tag[maxn << 2], sum[maxn << 2];
inline void clear() {
memset(tag, 0, sizeof(tag));
memset(sum, 0, sizeof(sum));
}

inline void pushtag(int l, int r, int p, int x) {
tag[p] += x;
sum[p] += (r - l + 1) * x;
}

inline void pushdown(int p, int l, int r) {
if(tag[p]) {
pushtag(l, mid, ls, tag[p]);
pushtag(mid + 1, r, rs, tag[p]);
tag[p] = 0;
}
}

inline void modify(int l, int r, int ql, int qr, int p, int x) {
if(ql > r || qr < l) return;
if(ql == l && qr == r) return pushtag(l, r, p, x);
pushdown(p, l, r);
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);
sum[p] = sum[ls] + sum[rs];
}

inline ll query(int l, int r, int ql, int qr, int p) {
if(l == ql && r == qr) return sum[p];
pushdown(p, l, r);
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
} ;

inline void calc() {
static int st[maxn], top, r[maxn], l[maxn];
static SEG T;
rep(i, 1, n) Q[i].clear();
rep(i, 1, n) M[i].clear();

a[n + 1] = inf; st[top = 1] = n + 1;
dep(i, n, 1) {
while(a[st[top]] < a[i]) top--;
r[i] = st[top] - 1; st[++top] = i;
// cerr << "r[" << i << "] = " << r[i] << endl;
}
a[0] = inf; st[top = 1] = 0;
rep(i, 1, n) {
while(a[st[top]] < a[i]) top--;
l[i] = st[top]; st[++top] = i;
}

rep(i, 1, m) Q[q[i].first.first].pb(mp(q[i].first.second, q[i].second));
T.clear();

rep(i, 1, n) {
if(l[i]) T.modify(1, n, i + 1, r[i], 1, p2), M[l[i]].pb(mp(i + 1, r[i]));
if(i != r[i]) T.modify(1, n, r[i] + 1, r[i] + 1, 1, p1);
}

rep(i, 1, n) {
for(auto v : Q[i]) ans[v.second] += T.query(1, n, i, v.first, 1);
for(auto v : M[i]) T.modify(1, n, v.first, v.second, 1, -p2);
if(i != r[i]) T.modify(1, n, r[i] + 1, r[i] + 1, 1, -p1);
}
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); m = read(); p1 = read(); p2 = read();
rep(i, 1, n) a[i] = read();
rep(i, 1, m) q[i].first.first = read(), q[i].first.second = read(), q[i].second = i;
calc();
reverse(a + 1, a + 1 + n);
rep(i, 1, m) {
q[i].first.first = n - q[i].first.first + 1;
q[i].first.second = n - q[i].first.second + 1;
swap(q[i].first.first, q[i].first.second);
}
calc();
rep(i, 1, m) printf("%lld\n", ans[i] + (q[i].first.second - q[i].first.first) * p1);
return 0;
}
/*
10 5 2 3
7 9 5 1 3 10 6 8 2 4
1 7
1 9
1 3
5 9
1 5
*/

礼物

给定两个长度为\(n\)的环\(a_i, b_i\), 可以任意旋转然后最小化下式: \[ \sum _ {i = 1} ^ n (a_i - b_i + c)^2 \] \(c\)为任意整数.

把式子展开一下有: \[ \begin{aligned}&\sum_{i = 1} ^ n(a_i-b_i)^2+2c(a_i-b_i)+c^2\\=&\sum_{i = 1}^na_i^2+\sum_{i=1}^nb_i^2-2\sum_i^na_ib_i+2c\left(\sum_{i=1}^na_i-\sum_{i=1}^nb_i\right)+nc^2\end{aligned} \]

有关\(c\)的式子是个二次函数,直接求最小值就好了.

\(A=\sum_{i=1}^na_ib_i\).

显然我们将\(b_i\)倍长,\(a_i\)翻转.求\(A\)的过程就变成了一个卷积的过程,所以直接\(\text{FFT}\)就好了.

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
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int maxn = 2e5 + 5;
const double zo = 0;

int n, m, a[maxn], b[maxn], sum, del;

ll ans = (1ll << 50);

namespace NTT{
const int P = (479 << 21) + 1, G = 3;
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){ll rnt = 1ll * x * y; return rnt >= P ? int(rnt % P) : int(rnt);}
int rev[maxn];
inline int pow(int x, int k){
int cnt = 1;
while(k){
if(k & 1)cnt = mul(cnt, x);
x = mul(x, x); k >>= 1;
} return cnt;
}
inline void dft(int *a, int n, int f){
for(register int i = 0; i < n; i++)
if(i < rev[i])swap(a[i], a[rev[i]]);
for(register int i = 1; i < n; i <<= 1){
int Wn = pow(f, (P - 1) / (i << 1));
for(register int j = 0; j < n; j += (i << 1)){
int w = 1;
for(register int k = 0; k < i; k++, w = mul(w, Wn)){
int A1 = a[j + k], A2 = mul(w, a[i + j + k]);
a[j + k] = pls(A1, A2); a[i + j + k] = dec(A1, A2);
}
}
}
}
inline void conv(int *a, int *b, int n, int m){
int s = 2, l = 1; while(s <= (n + m))s <<= 1, l++;
for(register int i = 0; i < s; i++)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));
dft(a, s, G); dft(b, s, G);
for(register int i = 0; i < s; i++)
a[i] = mul(a[i], b[i]);
dft(a, s, pow(G, P - 2)); int inv = pow(s, P - 2);
for(register int i = 0; i <= n + m; i++)
a[i] = mul(a[i], inv);
}
}
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 main(){
n = read(); m = read();
for(register int i = 1; i <= n; i++)
a[n - i + 1] = read(), sum += a[n - i + 1] * a[n - i + 1], del += a[n - i + 1];
for(register int i = 1; i <= n; i++)
b[i] = read(), sum += b[i] * b[i], del -= b[i];
NTT :: conv(a, b, n, n);
for(register int i = 1; i <= n; i++){
int A = n, B = 2 * del, C = sum - 2 * (a[i] + a[n + i]);
ll de = 1ll * B * B - 1ll * 4 * A * C;
double x = 0;
x = -B / double(2 * A);
ll x0 = x;
ans = min(ans, A * x0 * x0 + B * x0 + C); x0++;
ans = min(ans, A * x0 * x0 + B * x0 + C); x0 -= 2;
ans = min(ans, A * x0 * x0 + B * x0 + C);
}
cout << ans;
return 0;
}

大佬

妙妙题...

首先得知道第一个结论就是:锤大佬和保命是两个独立的东西.

所以我们直接先\(\text{dp}\)出我们可以在活下来的前提下最多剩下多少天.

假设最多能剩下\(Liv\)天.

问题就变成了你能不能在\(Liv\)天内凑出\(C\).

然后我们证明发现在\(\text{100}\)天内能凑出来的不同的\(F\)并不多.这个可以直接搜出来.(黑人问号?)

然后问题变成了给你若干个二元组\((F_i,d_i)\),你需要选出来两个二元组\(i,j\)使得: \[ \begin{aligned}d_i+d_j &\le Liv\\F_i+F_j &\le C\\F_i+F_j+Liv&-d_i-d_j\ge C\end{aligned} \]

然后发现(发现失败)如果\(3\)式和\(2\)式都成立,就可以直接约束\(1\)式了.所以我们只用考虑\(2,3\)式,用两个单调指针扫扫就好了.(特别鸣谢\(\text{Itst}​\))

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
/*
* 4828.cpp
* This file is part of BZOJ_4828
*
* Copyright (C) 2019 - ViXbob
*
* BZOJ_4828 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_4828 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_4828. 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 id(x, y) (1000 + (x - 1) * n + y)

typedef unsigned long long ull;
typedef long long ll;

using namespace std;

const int maxn = 1e2 + 5;
const int inf = 0x3f3f3f3f;
const int maxS = 2e6 + 5;
struct pair_hash {
template <class T1, class T2>
std::size_t operator () (const std::pair<T1, T2> &p) const {
auto h1 = std::hash<T1>{}(p.first);
auto h2 = std::hash<T2>{}(p.second);
return h1 ^ h2;
}
};
int n, m, Lim, a[maxn], w[maxn], c[maxn], f[maxn][maxn], live, tot, mxc, pre[maxS], btot;
unordered_map<pair<int, int>, bool, pair_hash> mp[maxn], pool;
pair<int, int> p[maxS], b[maxS];

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 main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stderr);
n = read(); m = read(); Lim = read();
rep(i, 1, n) a[i] = read();
rep(i, 1, n) w[i] = read();
rep(i, 1, m) c[i] = read(), mxc = max(c[i], mxc);
/* ----------------------------------- */
rep(i, 0, n - 1) rep(j, a[i + 1], Lim) {
int nxt = min(j + w[i + 1] - a[i + 1], Lim);
f[i + 1][nxt] = max(f[i + 1][nxt], f[i][j]);
f[i + 1][j - a[i + 1]] = max(f[i + 1][j - a[i + 1]], f[i][j] + 1);
}
rep(i, 1, n) rep(j, 0, Lim) live = max(live, f[i][j]);
/* ----------------------------------- */
queue<pair<int, pair<int, int>> > q;
q.push(mp(1, mp(0, 1)));
while(q.size()) {
int d = q.front().first, L = q.front().second.first, F = q.front().second.second; q.pop();
if(!pool[mp(F, d)]) b[++btot] = mp(F, d), pool[mp(F, d)] = 1;
if(d >= live) continue;
if(1ll * L * F <= mxc && L > 1 && !mp[d + 1].count(mp(L, L * F))) {
q.push(mp(d + 1, mp(L, L * F))); mp[d + 1][mp(L, L * F)] = 1;
}
if(1ll * (L + 1) * F <= mxc && !mp[d + 1].count(mp(L + 1, F)))
q.push(mp(d + 1, mp(L + 1, F))), mp[d + 1][mp(L + 1, F)] = 1;
}
/* ----------------------------------- */
// cerr << live << endl;
// cerr << tot << endl;
// sort(p + 1, p + 1 + tot);
sort(b + 1, b + 1 + btot);
rep(i, 1, btot) if(b[i].first != b[i - 1].first) p[++tot] = b[i];
// rep(i, 1, tot) cerr << p[i].first << " " << p[i].second << endl;
rep(i, 1, m) {
if(c[i] <= live) { puts("1"); continue; }
int judge = 0, R = 1, mx = -inf;
dep(j, tot, 1) {
while(p[j].first + p[R].first <= c[i] && R <= tot)
mx = max(mx, p[R].first - p[R].second), R++;
if(mx + p[j].first - p[j].second + live >= c[i]) { judge = 1; break; }
if(p[j].first <= c[i] && p[j].first - p[j].second + live >= c[i]) { judge = 1; break; }
} putchar(judge + '0'); putchar('\n');
}
return 0;
}
/*
*/

队长快跑

\(\color{red}{nan}\)了,不会做,先挖坑.

抛硬币

直接做好像都有\(70\)??

我们将两个人抛硬币的序列看成两个个\(01\)序列.(正面向上为\(1\),反面向上为\(0\))

先考虑考虑\(a=b\)的情况:

\(a=b\)时所有小\(A\)获胜的情况的两人的\(01\)序列中的\(0\)\(1\), \(1\)\(0\)一定是一个小\(B\)获胜的情况.

所以可以知道小\(B\)获胜的次数和小\(A\)获胜的次数应该是相同的.所以答案为总方案减去平局方案除二: \[ \begin{aligned}ans &= \frac{2^{a+b}-\sum_{i=0}^a\binom{a}{i}^2}{2}\\&=\frac{2^{a+b}-\binom{2a}{a}}{2}\end{aligned} \]

\(a\ne b\)的情况:

由于\(a > b\)所以小\(A\)和小\(B\)获胜的次数并不相同了, 但是发现因为\(a>b\)所以当小\(B\)获胜或者平局的情况中的序列\(01\)翻转后一定是小\(A\)获胜.和\(a=b\)的情况有不同的就是当小\(A\)获胜时的情况的序列\(01\)翻转后不一定是小\(B\)获胜, 即有可能还是小\(A\)获胜.

设小\(A\)获胜并且序列\(01\)翻转后还是小\(A\)获胜的方案数为\(Sa\).

所以答案就是总方案数减去\(Sa\)除二再加上\(Sa\).现在考虑\(Sa\)怎么求:

设小\(A\)\(01\)序列中\(1\)的个数为\(A\), 小\(B\)的为\(B\).根据\(Sa\)的定义则有不等式: \[ \begin{aligned}A&>B\\a-A&>b-B\end{aligned} \] 解得:\(0<A-B<a-b\).(出题人也默契的写出了a-b<=1e4)则有: \[ \begin{aligned}Sa&=\sum_{B=0}^{b}\sum_{i=1}^{a-b-1}\binom{b}{B}\binom{a}{B+i}\\&=\sum_{i= 1} ^ {a - b - 1} \sum_{B = 0} ^ b\binom{b}{b-B}\binom{a}{B+i}\\&=\sum_{i=1}^{a-b-1}\binom{a+b}{b+i}\end{aligned} \] 则答案为: \[ ans=\frac{2^{a+b}+\sum_{i = 1} ^ {a - b - 1}\binom{a+b}{b+i}}{2} \] 但是\(2\)在膜\(10^k\)意义下好像没有逆元啊....(毒瘤出题人)

这需要用到一些组合数的对称性,则有: \[ \frac{\binom{2a}{a}}{2}=\binom{2a-1}{a} \]

并且\(\sum_{i=1}^{a-b-1}\binom{a+b}{b+i}\)求得刚好是一段关于\(\frac{a+b}{2}\)对称的一个区间,所以只算一半就好了,当然如果\(a+b\)为偶数时要把中间的那一个单独加上.

PS: \[ \begin{aligned}\frac{\binom{2a}{a}}{2}&=\binom{2a}{a}\times \frac{1}{2}\\&=\frac{(2a)!}{a!\times a!}\times\frac{1}{2}\\&=\frac{(2a-1)!\times 2a}{a!\times(a-1)!\times a}\times \frac{1}{2}\\&=\frac{(2a-1)!}{a!\times (a-1)!}=\binom{2a-1}{a}\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
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
/*
* 4830.cpp
* This file is part of BZOJ_4830
*
* Copyright (C) 2019 - ViXbob
*
* BZOJ_4830 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_4830 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_4830. 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 id(x, y) (1000 + (x - 1) * n + y)

typedef unsigned long long ull;
typedef long long ll;

using namespace std;

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

int k, fac[2][maxn], p, p0, p1, inv0, inv1;
ll a, b;

inline void PreSolve() {
fac[0][0] = fac[1][0] = 1;
rep(i, 1, 512) fac[0][i] = (i & 1 ? 1ll * fac[0][i - 1] * i % 512 : fac[0][i - 1]);
rep(i, 1, 1953125) fac[1][i] = (i % 5 ? 1ll * fac[1][i - 1] * i % 1953125 : fac[1][i - 1]);
}

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

inline int Exgcd(int a, int b, int &x, int &y) {
if(b == 0) { x = 1; y = 0; return a; }
int x0, y0, d;
d = Exgcd(b, a % b, x0, y0);
x = y0; y = x0 - (a / b) * y0;
return d;
}

inline int inv(const int &a, const int &P, int x = 0, int y = 0) {
Exgcd(a, P, x, y); return (x + P) % P;
}

inline int Fac(ll n, int pi, int pk, int rnt = 1) {
if(n <= 1) return 1;
rnt = 1ll * ksm(fac[pi != 2][pk] % pk, n / pk, pk) * fac[pi != 2][n % pk] % pk;
return 1ll * rnt * Fac(n / pi, pi, pk) % pk;
}

inline int C(ll n, ll m, int pi, int pk) {
int tim = 0;
for(ll i = n; i; i /= pi) tim += i / pi;
for(ll i = m; i; i /= pi) tim -= i / pi;
for(ll i = n - m; i; i /= pi) tim -= i / pi;
if(tim >= k) return 0;
int C1 = Fac(n, pi, pk), C2 = Fac(n - m, pi, pk), C3 = Fac(m, pi, pk);
return 1ll * C1 * inv(C2, pk) % pk * inv(C3, pk) % pk * ksm(pi, tim, pk) % pk;
}

inline int China(ll n, ll m, int rnt = 0) {
rnt = pls(rnt, mul(C(n, m, 2, p0), inv0, p1, p), p);
rnt = pls(rnt, mul(C(n, m, 5, p1), inv1, p0, p), p);
return rnt;
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
PreSolve();
// cerr << fac[0][10] << endl;
while(~scanf("%lld%lld%d", &a, &b, &k)) {
p = ksm(10, k, inf); p0 = 1 << k; p1 = p / p0;
int ans = ksm(2, a + b - 1, p);
inv0 = inv(p1, p0); inv1 = inv(p0, p1);
if(a == b) ans = dec(ans, China((a << 1) - 1, a), p);
else {
rep(i, 1, a - b - 1 >> 1) ans = pls(ans, China(a + b, b + i), p);
if(a - b - 1 & 1) ans = pls(ans, China(a + b - 1, a + b >> 1), p);
}
// cerr << ans << endl;
while(ans < p / 10) putchar('0'), p /= 10;
printf("%d\n", ans);
}
return 0;
}
/*
3 2
3 * 1 + 3 * 3 + 1 * 4
3 + 9 + 4
*/