8.23 校内模拟赛题解报告

8.23 校内模拟赛题解报告

8.23 校内模拟赛题解报告

扯

花式白给

T1 SB 数论题苟比结论题不过我过了(笑

T2 鬼畜构造题完全木有想到暴力骗分苟命

T3 神仙二分题压根不会 (O(n^2)) 苟命

大概这场考试就是这样...

关于考试过程以及一些题外话

这次考试是从 T3 开的... 于是就把人玩没了

看题嗯 10 分 (O(n^2)) 送的

看题嗯好像就会 10 分的亚子

看题嗯确实就会 10 分的亚子

划拉了半张打草纸之后...

看题嗯...

然后就把那十分写了滚蛋了

回去老老实实看 T1

看题嗯这啥啊

看题嗯好像能做

看题嗯好像确实能做

在纸上划拉了一会...

看题嗯 SB 题

虽然 BS 这个题的代码写的很 SB 但是确实是把大样例过掉了

去骗 T2

先拿了那十分的暴力然后写掉二十分的构造然后就没有然后了...

看题好像不太可做的亚子

于是死磕 T3 嗝屁了

结束以后由于老吕没来

SB 的 BS 对着电脑捣鼓了半个小时依旧没把评测的东西弄好然后评测一直拖到了下午...

得分情况

100 + 30 + 10 = 140

虽然 T1 的代码很诡异但是还是过掉了

T2 和 T3 的暴力都没挂骗到了四十大概也就是 T1 的水平了...

题解

T1 Count

要结论的话很简单

枚举 ([1, p)) 范围内的所有数 (i) 记录 (i^2 equiv 1 pmod p) 的数的数量

答案: (ans = left lfloor frac {varphi(p) - cnt}2 ight floor + cnt)

Q: 为什么

题目要求满足

[xy equiv 1 pmod p ]

的无序二元组个数

看一下上面那个东西大概就能看出来了就是个逆元

这里的 (p) 不一定是质数所以逆元不一定存在当 (a ot p) 时 (a) 存在模 (p) 意义下的逆元且逆元唯一

所以这个题就相当于求与 (p) 互质的数的个数显然就是 (varphi(p)) 了

但是题目里要求的无序二元组而每一个与 (p) 互质的 (x) 都对应着一个 (y) 当 (x e y) 的时候就会算重所以这就是上面统计平方模 (p) 为 (1) 的数的个数的原因了

求那个 (varphi) 的时候以为只能用素数去筛于是就先把素数筛出来再用素数筛 (varphi) 忘记可以直接 (sqrt n) 求了...

于是就写了一个线筛筛素数不晒 (varphi) 函数筛完素数拿着筛出来的素数又把 (varphi) 求了一遍的诡异代码

代码

/*
  Source: count
*/
#include<cstdio>
#include<cstring>
#define int long long
#define pt putchar(' ')
#define pn putchar('
')
#define Abs(x) ((x) < 0 ? -(x) : (x))
#define Max(x, y) ((x) > (y) ? (x) : (y))
#define Min(x, y) ((x) < (y) ? (x) : (y))
#define Swap(x, y) ((x) ^= (y) ^= (x) ^= (y))
/*----------------------------------------------------------*/
const int A = 1e4 + 7;
const int B = 1e5 + 7;
const int C = 1e6 + 7;
const int D = 5e7 + 7;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
/*----------------------------------------------------------*/
inline void File() {
	freopen("count.in", "r", stdin);
	freopen("count.out", "w", stdout);
}
/*----------------------------------------------------------*/
int p, prime[C << 2], cnt, kcnt, Phi;
bool vis[D];
/*----------------------------------------------------------*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
void Print(int x) {if(x < 0) putchar('-'), x = -x; if(x > 9) Print(x / 10); putchar(x % 10 ^ 48);}
/*----------------------------------------------------------*/
int power(int x, int y) {int res = 1; for(; y; x = x * x % p, y >>= 1) if(y & 1) res = res * x % p; return res;}
void exgcd(int a, int b, int &d, int &x, int &y)
{
	if(b) exgcd(b, a % b, d, y, x), y -= x * (a / b);
	else d = a, x = 1, y = 0;
}
void pre() {
	for(int i = 2; i ^ p + 1; i++)
	{
		if(!vis[i]) prime[++cnt] = i;
		for(int j = 1; j ^ cnt + 1 && i * prime[j] <= p; j++)
		{
			vis[i * prime[j]] = 1;
			if(!(i % prime[j])) break;
		}
	}
}
void Main() {
	File();
	Phi = p = read(); pre();
	for(int i = 1; i ^ p; i++) if(i * i % p == 1) kcnt++;
	for(int i = 1; i ^ cnt + 1 && prime[i] * prime[i] <= p; i++) if(!(p % prime[i]))
	{
		Phi = Phi / prime[i] * (prime[i] - 1);
		while(!(p % prime[i])) p /= prime[i];
	}
	if(p > 1) Phi = Phi / p * (p - 1);
	Print((Phi - kcnt >> 1) + kcnt);
}
/*----------------------------------------------------------*/
signed main() {Main(); return 0;}

T3 Sequence

神仙分治题

由于过于麻烦这里直接说做法了

取 (mid = left lfloor frac {l + r}2 ight floor) 对左边维护后缀最大值记为 (max) 后缀最小值记为 (min) 右边维护前缀最大值(max) 前缀最小值(min) 前缀最大值的前缀和(summax) 前缀最小值的前缀和(summin) 前缀最大值与最小值的乘积和(summul)

枚举左侧每个位置对每个 (i) 找到第一个位置 (tmp1) 使 (min_{tmp1} leq min_i) 且 (min_{tmp1 - 1} > min_i) 同时找到第一个位置 (tmp2) 使 (max_{tmp2} geq max_i) 且 (max_{tmp2 - 1} < max_i) 将右边的区间分为三段利用上面维护的各种东西就可以 (O(1)) 的算出右端点在右边区间内的价值和

递归处理左右两部分

各种边界细节问题极其鬼畜

代码

/*
  Source: T196991 Sequence
*/
#include<cstdio>
#define int long long
#define Max(x, y) ((x) > (y) ? (x) : (y))
#define Min(x, y) ((x) < (y) ? (x) : (y))
/*----------------------------------------------------------*/
const int B = 5e5 + 7;
const int mod = 998244353;
/*----------------------------------------------------------*/
int n, a[B], min[B], max[B], summin[B], summax[B], summul[B], ans;
/*----------------------------------------------------------*/
inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
void Print(int x) {if(x < 0) putchar('-'), x = -x; if(x > 9) Print(x / 10); putchar(x % 10 ^ 48);}
/*----------------------------------------------------------*/
void solve(int L, int R) {
	if(L == R) {ans = (ans + a[L] * a[L] % mod) % mod; return ;}
	int Mid = L + R >> 1;
	min[Mid] = max[Mid] = a[Mid]; min[Mid + 1] = max[Mid + 1] = a[Mid + 1];
	summin[Mid] = summax[Mid] = summul[Mid] = 0;
	summin[Mid + 1] = summax[Mid + 1] = a[Mid + 1]; summul[Mid + 1] = a[Mid + 1] * a[Mid + 1] % mod;
	for(int i = Mid - 1; i >= L; i--)
		min[i] = Min(min[i + 1], a[i]), max[i] = Max(max[i + 1], a[i]);
	for(int i = Mid + 2; i <= R; i++)
		min[i] = Min(min[i - 1], a[i]), summin[i] = (summin[i - 1] + min[i]) % mod,
		max[i] = Max(max[i - 1], a[i]), summax[i] = (summax[i - 1] + max[i]) % mod,
		summul[i] = (summul[i - 1] + min[i] * max[i] % mod) % mod;
	for(int i = Mid, tmp1 = Mid + 1, tmp2 = Mid + 1; i >= L; i--)
	{
		while(tmp1 <= R && min[tmp1] > min[i]) tmp1++;
		while(tmp2 <= R && max[tmp2] < max[i]) tmp2++;
		int x = Min(tmp1, tmp2), y = Max(tmp1, tmp2);
		ans = (ans + (x - 1 - Mid) * min[i] % mod * max[i] % mod) % mod;
		if(tmp1 < tmp2) ans = (ans + (summin[tmp2 - 1] - summin[tmp1 - 1]) % mod * max[i] % mod) % mod;
		if(tmp1 > tmp2) ans = (ans + (summax[tmp1 - 1] - summax[tmp2 - 1]) % mod * min[i] % mod) % mod;
		ans = ((ans + summul[R] - summul[y - 1]) % mod + mod) % mod;
	}
	solve(L, Mid); solve(Mid + 1, R);
}
void Main() {
	n = read();
	for(int i = 1; i ^ n + 1; i++) a[i] = read();
	solve(1, n);
	Print(ans);
}
/*----------------------------------------------------------*/
signed main() {Main(); return 0;}