• 前言：
• T1 count
• T2 color (CF547D Mike and Fish)
• T3 Sequence

前言：

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