前言：
\(T1\) 逆元。
\(T2\) 没过大样例竟然跑过去了 = =
\(T3\) 没开 \(long ~long\) 含泪挂 0
期望： \(Soce: 20 + 60 + 10\)
实际： \(Soce: 20 + 100 + 0\)
T1 count
一道 sb 数论题。
题目大意：
问有几个无序二元组 \((x, y)\) 满足 \(x y ≡ 1 \pmod p\), \(0 ≤ x < P, 0 ≤ y <P\)。
solution
发现 \(xy \equiv 1(mod~p)\) 实际上就是 \(x\) 逆元的定义式。
\(x\) 有逆元当且仅当 \(gcd(x, p) = 1\) 的时候，并且逆元是唯一的。
设 \(1\sim P - 1\) 中与 \(P\) 互质的数有 \(s\) 个，考虑这 \(s\) 个数与它
们的逆元组成的二元组，这些二元组一定符合条件，那么只要考
虑去重的问题。
可以发现如果 $xy \equiv 1(modp), x\neq y $那么 \((x,y)\) 和 \((y,x)\)
一定会在上述 s 个二元组中各出现一次，也就是被多算了一次。
当 \(x = y\) 的时候，\((x, x)\) 这个二元组只会出现一次，设个数为 \(t\) 个。
答案就是 \(\frac{s + t}{2}\)。
\(1\sim P - 1\) 中与 \(P\) 互质的数的个数用欧拉函数来求就好。
code
/*
work by:Ariel_
Knowledge:
Time:
*/
#include <bits/stdc++.h>
#define ll long long
#define rg register
using namespace std;
int p, Ans;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int phi(int m) {
int res = m, tmp = m;
for (int i = 2; i * i <= m; i++) {
if (tmp % i == 0) {
res = res / i * (i - 1);
while(tmp % i == 0) tmp /= i;
}
}
if (tmp > 1) res = res / tmp * (tmp - 1);
return res;
}
int main(){
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
p = read();
Ans += phi(p);
for(int i = 1; i <= p; i++)
if(i * i % p == 1) Ans++;
Ans = Ans / 2;
printf("%d\n", Ans);
return 0;
}
T2 color (CF547D Mike and Fish)
一道 CF 原题
solution
对于 \(x\) 坐标相同的点，把这些点两两配对，如果剩下点则不管，然后在每一对点之间连一条边。
对于 \(y\) 坐标相等的点，把这些点两两配对，如果剩下点则不管，然后在每一对点之间连一条边。
最后对得到的图进行黑白染色可以得到我们的方案了。
证明：如果我们红蓝染色成功，那么对于每一个 \(x\) 或者 \(y\) 坐标来讲最多剩一个点，这个点的颜色可以任意选择。
code
/*
work by:Ariel_
Knowledge:
Time:
*/
#include <bits/stdc++.h>
#define rg register
using namespace std;
const int N = 500010;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int n, x, y, col[N];
map<int, int>lx, ly;
int head[N], E;
char c[2];
struct edge{int v, nxt;}e[N << 1];
void add_edge(int u, int v) {
e[++E] = (edge) {v, head[u]};
head[u] = E;
}
void dfs(int u, int f){
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if (v == f) continue;
if(col[v] == -1) {
col[v] = col[u] ^ 1;
dfs(v, u);
}
}
}
int main(){
//freopen("color.in", "r", stdin);
//freopen("color.out", "w", stdout);
n = read();
memset(col, -1, sizeof col);
c[0] = 'r', c[1] = 'b';
for (int i = 1; i <= n; i++) {
x = read(), y = read();
if(lx[x]) {
add_edge(lx[x], i), add_edge(i, lx[x]);
lx[x] = 0;
} else lx[x] = i;
if (ly[y]) {
add_edge(ly[y], i), add_edge(i, ly[y]);
ly[y] = 0;
} else ly[y] = i;
}
for (int i = 1; i <= n; i++)
if(col[i] == -1) col[i] = 1, dfs(i, 0);
for (int i = 1; i <= n; i++) printf("%c", c[col[i]]);
puts("");
return 0;
}
/*
10
1 1
2 1
2 2
3 2
4 3
4 4
3 3
2 3
2 4
1 3
*/
T3 Sequence
很有价值的一道题。
给出一个 \(n\) 个数的序列，一个区间的价值是区间内最小值乘最大值的积。
\(n\leq 10^5\)
考试的时候一直在考虑每个数对哪些区间有贡献，把贡献对应到二维平面上，求解。
写数据结构写多了吧 = = 没注意到 \(n\leq 10^5\)
感觉题解解释的就很详细了，所以就直接搬来了。（其实是我懒）
subtask1
\(O(n^2)\) 暴力
subtask2
数据是随机的。
考虑分治。
如果当前是在考虑区间 \([l,r]\) 的子区间的价值和，设区间 \([l, r]\) 内最大值的下标为 \(mid\) 。
考虑左端点在 \([l, mid]\) 内，右端点在 \([mid,r ]\) 内的区间的价值和。它们内部的最大值是 \(a_{mid}\) 。
对 \([l, mid]\) 做后缀 \(\min\) ，对 \([mid, r]\) 做前缀 \(\min\) ，不妨把结果记为\(mn[i]\) 。即 \(l\leq i\leq mid\) 时，\(mn[i] = min_{i = l}^{mid }a_i\) ；\(mid < i \leq r\) 时 \(mn[i] = min_{i = mid}^r a_i\) 。
枚举左端点，由于右半部分的 \(mn\) 是单调的，一定存在一个分界点 \(p\) ，使得 \(j \leq p\) 时，\(mn[j] \geq mn[i]\) ，\(j > p\) 时 \(mn[j] < mn[i]\) 。又由于左半部分的 \(mn\) 也是单调的，所以左端点 \(i\) 移动的时，分界点 \(p\) 的移动方向是不变的。这样就容易对每个左端点 \(i\) 都求出分界点 \(p\) 了。另外再求出 \(mn\) 的前缀和，就能 \(O(1)\) 求出左端点在 \(i\) ， 右端点在 \([mid, r]\) 内的区间的价值和了。
然后递归计算区间 \([l, mid - 1]\) 和 \([mid + 1, r]\)
时间复杂度 \(O(nlogn)\)
Subtask3
只有 10 种数，因此左端点固定时，最大值至多只有 10 种，
即右端点在某段区间内的最大值相同，而这种区间最多只有 10 个。
最小值同理。同时考虑最大值和最小值可以知道，左端点固定时，右端点在某段区间内的最大值和最小值都相同，而这种区间最多只有 20 个。
移动左端点，用单调栈维护这些区间。复杂度 \(O(n \times 20)\)
Subtask5
跟 Subtask2 的做法类似，每次取 $mid = \lfloor \frac{l + r}{2}\rfloor $，对最大值进行和最小值类似的操作（不妨把前缀/后缀 \(\max\) 的结果记为 \(mx[i]\) ）。我们可以求出最大值的分界点 \(q\)。除了 \(mn\) 的前缀和外，再求出 \(mx\) 的前缀和以及 \(mn \times mx\) 的前缀和。\(p\) 和 \(q\) 把右半部分划分成三个区间，对三个区间分别计算。利用求出来的前缀和可以 \(O(1)\) 算出右端点在一个区间内的价值和。
然后再递归计算左右两半部分。
code
/*
work by:Ariel_
Knowledge:
Time:
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#define ll long long
#define rg register
using namespace std;
const ll mod = 998244353;
const int MAXN = 1e6 + 5;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int n, a[MAXN], Ans, mn[MAXN], mx[MAXN], s1[MAXN], s2[MAXN], s3[MAXN];
void work(int l, int r) {
if (l == r) {
Ans = (Ans + 1ll * a[l] * a[r] % mod) % mod;
return ;
}
int mid = l + r >> 1;
mn[mid] = a[mid];
for (int i = mid - 1; i >= l; i--) mn[i] = min(mn[i + 1], a[i]);
mx[mid] = a[mid];
for (int i = mid - 1; i >= l; i--) mx[i] = max(mx[i + 1], a[i]);
mn[mid + 1] = a[mid + 1];
for (int i = mid + 2; i <= r; i++) mn[i] = min(mn[i - 1], a[i]);
mx[mid + 1] = a[mid + 1];
for (int i = mid + 2; i <= r; i++) mx[i] = max(mx[i - 1], a[i]);
s1[mid] = 0;
for (int i = mid + 1; i <= r; i++) s1[i] = (s1[i - 1] + mn[i]) % mod;
s2[mid] = 0;
for (int i = mid + 1; i <= r; i++) s2[i] = (s2[i - 1] + mx[i]) % mod;
s3[mid] = 0;
for (int i = mid + 1; i <= r; i++) s3[i] = (s3[i - 1] + 1ll * mx[i] * mn[i] % mod) % mod;
int p1 = mid + 1, p2 = mid + 1;
for (int i = mid; i >= l; i--) {
while (p1 <= r && mn[p1] > mn[i]) p1++;
while (p2 <= r && mx[p2] < mx[i]) p2++;
if (p1 < p2) {
Ans = (Ans + 1ll * mn[i] * mx[i] % mod * (p1 - 1 - mid) % mod) % mod;
Ans = (Ans + 1ll * mx[i] * (s1[p2 - 1] - s1[p1 - 1] + mod) % mod) % mod;
Ans = (Ans + (s3[r] - s3[p2 - 1] + mod) % mod) % mod;
}
else {
Ans = (Ans + 1ll * mn[i] * mx[i] % mod * (p2 - 1 - mid) % mod) % mod;
Ans = (Ans + 1ll * mn[i] * (s2[p1 - 1] - s2[p2 - 1] + mod) % mod) % mod;
Ans = (Ans + (s3[r] - s3[p1 - 1] + mod) % mod) % mod;
}
}
work(l, mid), work(mid + 1, r);
}
int main(){
n = read();
for (int i = 1; i <= n; i++) a[i] = read();
work(1, n);
printf("%d", Ans);
puts("");
return 0;
}