BJOI2019

BJOI2019

奥术神杖

要求最大化: \[ \left(\prod_{i=1}^nV_i\right)^{\frac{1}{c}} \] 考虑对这个式子取对数,那么根据对数运算法则这个式子就变成了: \[ \frac{\sum_{i=1}^n\log V_i}{c} \] 这个是一个经典的分数规划模型,我们二分答案后,在\(\text{AC}\)自动机上\(\text{dp}\)就可解决这个问题了,具体的:我们设\(f[i][j]\)表示匹配到串的第\(i\)个字符在\(\text{AC}\)机上的\(j\)状态上的最优解。如果\(i\)这一位是"."就枚举这一位的字符,否则只转移原串中的字符就行了。

PS:在建\(\text{fail}\)指针时直接将每个点的\(\text{fail}\)节点的权值累加到这个点上,就是这个点最终的权值。

代码:

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

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 2e3 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;
const double eps = 1e-10;

int n, m, V[maxn];
int ch[maxn][10], fail[maxn], cnt, con[maxn], pre[maxn][maxn];
vector<int> ed[maxn];
double w[maxn], f[maxn][maxn], nw[maxn], Mx;
char s[maxn], t[maxn], ans[maxn], num[maxn][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 dcmp(double x, double y) { return fabs(x - y) <= eps ? 0 : (x > y ? 1 : -1); }

inline void insert(int id, int u = 0) {
scanf("%s", t + 1);
for(int i = 1; t[i]; i++) {
if(!ch[u][t[i] - '0']) ch[u][t[i] - '0'] = ++cnt;
u = ch[u][t[i] - '0'];
} ed[u].pb(id);
}

inline void BuildFail() {
queue<int> q;
rep(i, 0, cnt) for(auto v : ed[i]) w[i] += log(V[v]), con[i]++;
rep(i, 0, 9) if(ch[0][i]) q.push(ch[0][i]);
while(q.size()) {
int u = q.front(); q.pop();
w[u] += w[fail[u]]; con[u] += con[fail[u]];
// cerr << "fail[" << u << "] = " << fail[u] << endl;
rep(i, 0, 9) {
int &v = ch[u][i];
if(!v) { v = ch[fail[u]][i]; continue; }
int k = fail[u];
while(!ch[k][i] && k) k = fail[k];
fail[v] = ch[k][i]; q.push(v);
}
}
}

inline void generatorstr(double mx = -eps, int M = 0, int p = n) {
rep(i, 0, cnt) if(f[n][i] > mx) mx = f[n][i], M = i;
while(p > 0) {
ans[p] = num[p][M];
M = pre[p][M]; p--;
}
}

inline bool check(double mid, double mx = -eps) {
rep(i, 0, cnt) nw[i] = w[i] - mid * con[i];
// rep(i, 0, cnt) cerr << "nw[" << i << "] = " << nw[i] << endl;
rep(i, 0, n) rep(j, 0, cnt) f[i][j] = -inf;
f[0][0] = 0;
rep(i, 0, n - 1) rep(j, 0, cnt) if(f[i][j] != -inf) {
if(s[i + 1] == '.') {
rep(k, 0, 9) if(f[i][j] + nw[ch[j][k]] > f[i + 1][ch[j][k]]) {
num[i + 1][ch[j][k]] = k + '0';
pre[i + 1][ch[j][k]] = j;
f[i + 1][ch[j][k]] = f[i][j] + nw[ch[j][k]];
}
} else if(f[i][j] + nw[ch[j][s[i + 1] - '0']] > f[i + 1][ch[j][s[i + 1] - '0']]) {
num[i + 1][ch[j][s[i + 1] - '0']] = s[i + 1];
pre[i + 1][ch[j][s[i + 1] - '0']] = j;
f[i + 1][ch[j][s[i + 1] - '0']] = f[i][j] + nw[ch[j][s[i + 1] - '0']];
}
}
rep(i, 0, cnt) mx = max(mx, f[n][i]);
return mx >= eps;
}

inline void Biniry(double l, double r) {
double mid, Ans;
while(dcmp(r, l) == 1) {
mid = (l + r) / 2;
if(check(mid)) Ans = mid, generatorstr(), l = mid + eps;
else r = mid - eps;
} //cerr << mid << endl;
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); m = read();
scanf("%s", s + 1);
rep(i, 1, m) insert(i), V[i] = read(), Mx = max(Mx, log(V[i]));
BuildFail();
// rep(i, 0, cnt) cerr << "w[" << i << "] = " << w[i] << ", con[" << i << "] = " << con[i] << endl;
// rep(i, 0, cnt) rep(j, 0, 1) cerr << "ch[" << i << "][" << j << "] = " << ch[i][j] << endl;
Biniry(0, Mx + eps);
// cerr << check(1) << endl;
rep(i, 1, n) putchar(ans[i]);
return 0;
}

勘破神机

又是二合一...

下文中\(x^{\underline{n}}\)表示\(x\)\(n\)次下降幂,即:\(x^{\underline{n}}=\prod_{i=1}^n(x-i+1)\)

先考虑第一问:

这个东西实际上就上要我们求: \[ \sum_{i=l}^r\binom{f[i]}{k} \] \(f[i] = fib[i+1]\).

考虑展开: \[ \sum_{i=l}^r\frac{f[i]^{\underline{k}}}{k!} \] 想的时候是往生成函数方面想的,你直接把\(x^{\underline{n}}\)看成一个\(n\)次多项式就可以把这个下降幂转成一个幂和的形式了。事后发现原来这个多项式的系数就是有符号第一类斯特林数.....(没学过,告辞)

然后有: \[ \frac{1}{k!}\sum_{i=l}^r\sum_{j=1}^k\begin{bmatrix}k\\j\end{bmatrix}_sf[i]^j \] 显然有\(f[i]\)的递推式: \[ \begin{cases}f[n]=1, 0\le n\le1\\f[n]=f[n-1]+f[n-2],n>1\end{cases} \] 然后我们用特征方程解一下可得: \[ f[n]=\frac{5+\sqrt5}{10}\left(\frac{1+\sqrt5}{2}\right)^n+\frac{5-\sqrt5}{10}\left(\frac{1-\sqrt5}{2}\right)^n \]\(f[n]\)可以被表示为\(A\alpha^n+B\beta^n\)的形式,我们把这个代回上式有: \[ \begin{aligned}&\frac{1}{k!}\sum_{i=l}^r\sum_{j=1}^k\begin{bmatrix}k\\j\end{bmatrix}_s\left(A\alpha^i+B\beta^i\right)^j\\=&\frac{1}{k!}\sum_{i=l}^r\sum_{j=1}^k\begin{bmatrix}k\\j\end{bmatrix}_s\sum_{v=0}^j\binom{j}{v}A^v\alpha^{iv}B^{j-v}\beta^{i(j-v)}\\=&\frac{1}{k!}\sum_{j=1}^k\begin{bmatrix}k\\j\end{bmatrix}_s\sum_{v=0}^j\binom{j}{v}A^vB^{j-v}\sum_{i=l}^r(\alpha^{v}\beta^{j-v})^i\end{aligned} \] 后面明显是个等差数列的形式直接用公式就好了。(注意存在公比为一的情况)

但是有个问题就是\(\sqrt5\)在膜\(998244353\)的意义下并不存在。我们可以尝试模仿复数,也搞一个"虚部"\(i\),只不过这个\(i^2=5\)。因为斐波那契数列最后求出来一定是个整数所以虚部的系数一定为\(0\).

考虑第二问:

先考虑求出这个东西的递推式,首先\(n\)为奇数的时候方案肯定等于零。所以我们设\(g_i\)表示\(n =2\times i\)的方案数。

考虑怎么递推,首先最后的一个\(3 \times 2\)的块中有三种摆放方式,但这一种转移肯定是漏掉了一些方案的,实则我们可以跨越最后一个偶数位置,如图:

然后我们枚举一下第二种情况跨越红线的数量就有递推式: \[ \begin{aligned}g[n]&=3\times g[n-1]+2\times\sum_{i=1}^{n-1}g[n-1-i]\\&=3 \times g[n-1]+2\times\sum_{i=0}^{n-2}g[i]\end{aligned} \] 则有: \[ \begin{cases}g[n]=3 \times g[n-1]+2\times\sum_{i=0}^{n-2}g[i]\\g[n+1]=3\times g[n]+2\times g[n-1]+2\times \sum_{i=0}^{n-2}g[i]\end{cases} \] 差分一下: \[ g[n+1]=4 \times g[n]-g[n-1] \] 也就是说\(g[n]\)的递推式为: \[ \begin{cases}g[n]=1,n=0\\g[n]=3,n=1\\g[n]=4 \times g[n-1]-g[n-2],n>1\end{cases} \] 用特征方程方程解得: \[ g[n]=\frac{3+\sqrt3}{6}(2+\sqrt3)^n+\frac{3-\sqrt3}{6}(2-\sqrt3)^n \] 然后就是一模一样的了。复杂度\(O(k^2 \log{(r-l)})\)

代码:

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
/*
* 3090.cpp
* This file is part of 3090
*
* Copyright (C) 2019 - ViXbob
*
* 3090 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.
*
* 3090 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 3090. 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 = 5e2 + 15;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

int T, m, k, sqr, C[maxn][maxn], S[maxn][maxn], V, ans, fac[maxn], ifac[maxn];
ll l, r, n, N;

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

struct Complex {
int x, y;
Complex(int a = 0, int b = 0) { x = a; y = b; }
Complex operator + (const Complex &t) const { return Complex((x + t.x) % P, (y + t.y) % P); }
Complex operator - (const Complex &t) const { return Complex((x - t.x + P) % P, (y - t.y + P) % P); }
Complex operator * (const Complex &t) const { return Complex((1ll * x * t.x % P + 1ll * V * y % P * t.y % P) % P, (1ll * x * t.y % P + 1ll * y * t.x % P) % P); }
Complex operator * (const int &t) const { return Complex(1ll * x * t % P, 1ll * y * t % P); }
} A, B, alpha, beta;

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, ll k, 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 Complex ksm(Complex x, ll k, Complex rnt = Complex(1, 0)) {
for(ll i = k; i; i >>= 1, x = x * x) if(i & 1) rnt = rnt * x;
return rnt;
}
inline Complex Inv(Complex a) { return Complex(a.x, P - a.y) * inv((1ll * a.x * a.x % P - 1ll * V * a.y % P * a.y % P + P) % P); }

const int inv2 = inv(2), inv10 = inv(10), inv6 = inv(6);

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
T = read(); m = read(); V = (m == 2) ? 5 : 3; S[1][1] = 1;
rep(i, 0, maxn - 1) C[i][0] = 1;
rep(i, 1, maxn - 1) rep(j, 1, i) C[i][j] = pls(C[i - 1][j - 1], C[i - 1][j]);
rep(i, 2, maxn - 1) rep(j, 1, i) S[i][j] = dec(S[i - 1][j - 1], mul(i - 1, S[i - 1][j]));
fac[0] = 1;
rep(i, 1, maxn - 1) fac[i] = 1ll * fac[i - 1] * i % P;
ifac[maxn - 1] = inv(fac[maxn - 1]);
dep(i, maxn - 2, 0) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
while(T--) {
l = read(); r = read(); k = read(); ans = 0; N = r - l + 1;
if(m == 2) {
A = Complex(inv2, inv10); B = Complex(inv2, P - inv10);
alpha = Complex(inv2, inv2); beta = Complex(inv2, P - inv2);
} else {
// l -= !(l & 1); r += (r & 1);
// l = l + 1 >> 1; r >>= 1;
l = l + 1 >> 1; r >>= 1;
A = Complex(inv2, inv6); B = Complex(inv2, P - inv6);
alpha = Complex(2, 1); beta = Complex(2, P - 1);
} n = r - l + 1;
// cerr << (A * ksm(alpha, 3) + B * ksm(beta, 3)).x << endl;
// cerr << l << " " << r << " " << n << endl;
rep(i, 1, k) {
Complex tmp(0, 0);
rep(j, 0, i) {
Complex c = ksm(A, j) * ksm(B, i - j);
Complex q = ksm(alpha, j) * ksm(beta, i - j);
Complex goal = (ksm(q, n + 1) - q) * Inv(q - Complex(1, 0));
if(q.x == 1 && q.y == 0) goal = q * (n % P);
tmp = tmp + c * goal * C[i][j] * ksm(q, l - 1);
}
// cerr << tmp.x << " " << tmp.y << " " << S[k][i] << endl;
ans = (ans + 1ll * S[k][i] * tmp.x % P) % P;
}
printf("%d\n", 1ll * ans * inv(N % P) % P * ifac[k] % P);
}
return 0;
}
/*
1 2 3 5
1 + 3 + 10
14 / 3
x
x(x-1)=-x+x^2
x(x-1)(x-2)=(x^2-x)(x-2)=2x-3x^2+x^3
(x^3-3x^2+2x)(x-3)=-6x+11x^2-6x^3+x^4

0 0 0 0 0 0 0 0 1 -1
0 0 0 0 0 0 0 1 -3 2
0 0 0 0 0 0 1 -6 11 -6
0 0 0 0 0 1 -10 35 -50 24

f[1]
f[2]
f[3] = f[1] * f[2]
f[4] = f[1] * f[2] ^ 2
f[5] = f[1] ^ 2 * f[2] ^ 3
f[6] = f[1] ^ 3 * f[2] ^ 5
f[7] = f[1] ^ 5 * f[2] ^ 8
f[n] = f[n - 1] * f[n - 2]
f[n] = f[1] ^ fib[n - 2] * f[2] ^ fib[n - 1];

1 1 2 3 5 8 13

*/

送别

咕咕咕....

排兵布阵

普及背包。

\(f[i][j]\)表示前\(i\)个堡垒用了\(j\)个士兵的最大收益。对于每个堡垒枚举一下可以打赢多少对手就好了。

复杂度\(O(nms)\)

代码:

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

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;

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 f[105][maxn], pre[105][105], s, n, m;

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

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
s = read(); n = read(); m = read();
rep(i, 1, s) rep(j, 1, n) pre[j][i] = read() * 2 + 1;
rep(i, 1, n) sort(pre[i] + 1, pre[i] + 1 + s), fill(f[i], f[i] + 1 + m, -inf);
fill(f[0], f[0] + 1 + m, -inf); f[0][0] = 0;
rep(i, 0, n - 1) rep(j, 0, m) if(f[i][j] != -inf)
rep(k, 0, s) {
int v = i + 1;
if(j + pre[v][k] <= m)
f[i + 1][j + pre[v][k]] = max(f[i + 1][j + pre[v][k]], f[i][j] + k * v);
else break;
}
int ans = 0;
rep(i, 0, m) ans = max(f[n][i], ans);
cout << ans << endl;
return 0;
}

光线

不知道为啥就是没想到可以把多块玻璃看成一块....降智了

\(f[i]\)表示前\(i\)块玻璃看成一块的透光率。(从第一块玻璃射入)

\(g[i]\)表示前\(i\)块玻璃看成一块的反射率。(从第\(i\)块玻璃射入)

我就很想知道为什么无论是从第一块玻璃射入的透光率还是第\(i\)块射入的透光率都是一样的。但是反射率却不同...

然后枚举一下一束光折射了多少次来转移则有: \[ \begin{aligned}f[i]&=f[i-1]a[i]\sum_{j=0}^{+\infin}(g[i-1]b[i])^j\\g[i]&=b[i]+a[i]^2g[i-1]\sum_{j=0}^{+\infin}(g[i-1]b[i])^j\end{aligned} \] 因为上式的等比数列的公比小于一所以直接上公式就好了,有: \[ \begin{aligned}f[i]&=\frac{f[i-1]a[i]}{1-g[i-1]b[i]}\\g[i]&=b[i]+\frac{a[i]^2g[i-1]}{1-g[i-1]b[i]}\end{aligned} \] 复杂度\(O(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
/*
* 3093.cpp
* This file is part of 3093
*
* Copyright (C) 2019 - ViXbob
*
* 3093 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.
*
* 3093 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 3093. 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 = 5e5 + 5;
const int P = 1e9 + 7;
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], f[maxn], g[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;
}

const int inv100 = inv(100);

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read();
rep(i, 1, n) a[i] = 1ll * read() * inv100 % P, b[i] = 1ll * read() * inv100 % P;
f[1] = a[1]; g[1] = b[1];
rep(i, 2, n) {
int inv = inv(dec(1, 1ll * g[i - 1] * b[i] % P));
f[i] = 1ll * f[i - 1] * a[i] % P * inv % P;
g[i] = pls(b[i], 1ll * g[i - 1] * mul(a[i], a[i]) % P * inv % P);
}
cout << f[n] << endl;
return 0;
}

删数

先考虑对于一个给定的序列怎么求出答案,设\(cnt[i]\)表示\(i\)出现的次数。

则答案为在值域\([1,n]\)上每个数\(i\)的覆盖区域为\([i-cnt[i]+1,i]\),最后没有被覆盖到的位置的数量。(不在值域\([1,n]\)内的数是不被算入的)

然后这个东西就是一个区间加一然后查询为\(0\)的位置的个数。我们可以直接在线段树上维护一个最小值,和最小值的个数来计算答案。

考虑修改:

首先单点修改只会影响两个数的出现次数,直接在线段树上单点修改一下就好了。(注意这个修改后的值是相对于你现在的查询区间的)

区间加一减一我们直接平移查询区间就好了,然后将两个端点上被移除区间的数的贡献减掉就好了。

注意因为要平移所以预留一下空间就好了。

复杂度\(O(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
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
/*
* 3094.cpp
* This file is part of 3094
*
* Copyright (C) 2019 - ViXbob
*
* 3094 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.
*
* 3094 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 3094. 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)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

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

int n, m, con[maxn], a[maxn], L, R, del, tot;

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

#define ls p << 1
#define rs p << 1 | 1
#define mid (l + r >> 1)
struct Node {
int sum, mn, con, tag;
Node(int a = 0, int b = 0, int c = 0, int d = 0) { sum = a; mn = b; con = c; tag = d; }
Node operator & (const Node &t) const {
int Mn = min(mn, t.mn);
int Con = (mn == Mn ? con : 0) + (t.mn == Mn ? t.con : 0);
int Sum = Mn ? 0 : Con;
return Node(Sum, Mn, Con);
}
} t[maxn << 2];

inline void Build(int l, int r, int p) {
if(l == r) return (void)(t[p] = Node(1, 0, 1));
Build(l, mid, ls); Build(mid + 1, r, rs);
t[p] = t[ls] & t[rs];
}

inline void pushtag(int p, int x) {
t[p].mn += x; t[p].tag += x;
t[p].sum = t[p].mn ? 0 : t[p].con;
}


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

inline void modify(int l, int r, int ql, int qr, int p, int x) {
if(ql > qr) return;
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 Node 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("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
n = read(); m = read(); del = max(n, m) + 5;
rep(i, 1, n) con[(a[i] = read()) + del]++;
L = 1; R = n; tot = del * 3 + n;
Build(1, tot, 1);
rep(i, 1, n) modify(1, tot, i - con[i + del] + 1 + 2 * del, i + 2 * del, 1, 1);
rep(i, 1, m) {
int p = read(), x = read();
if(p == 0) {
if(x == -1) {
modify(1, tot, L - con[L + del] + 1 + 2 * del, L + 2 * del, 1, -1);
L++; R++;
modify(1, tot, R - con[R + del] + 1 + 2 * del, R + 2 * del, 1, 1);
} else {
modify(1, tot, R - con[R + del] + 1 + 2 * del, R + 2 * del, 1, -1);
L--; R--;
modify(1, tot, L - con[L + del] + 1 + 2 * del, L + 2 * del, 1, 1);
}
} else {
x = L + x - 1;
if(a[p] >= L && a[p] <= R) modify(1, tot, a[p] - con[a[p] + del] + 1 + 2 * del, a[p] - con[a[p] + del] + 1 + 2 * del, 1, -1);
con[a[p] + del]--; con[x + del]++;
modify(1, tot, x - con[x + del] + 1 + 2 * del, x - con[x + del] + 1 + 2 * del, 1, 1);
a[p] = x;
}
printf("%d\n", query(1, tot, L + 2 * del, R + 2 * del, 1).sum);
}
return 0;
}

写个题解竟然写了整整两个小时.....自闭.jpg