一场 NOIP 模拟赛

2023-10-22 23:52:28

日均一千题，题量破百万！

上句为机房*魔怔人发言。

考前白嫖模拟赛当然要打，而且质量挺高的（叭

D 太毒瘤了所以跳了，B 卡不动常数了所以不卡了。

$\mathcal A$

给定质数 $p$ 和正整数 $a,b$，求最小正整数 $x$ 使得 $(p^a-1)\equiv 1\pmod {p^b-1}$。

输出 $x\bmod 998244353$，$a,b\leq 10^{18},p\leq 10^9$。

数论签到？认真的吗，虽然确实签到成功了（

都知道 $a\equiv 1\pmod b$ 的充要条件是 $(a,b)=1$，所以 $p>2$ 统统无解。

设 $f(a)=p^a-1$，发现这东西的一些性质：

$f(a)\bmod f(b)=f(a\bmod b)$
$\gcd(f(a),f(b))=f(\gcd(a,b))$

证了第一个就能推第二个了，根据朴素的辗转相除即可证明。

对于 $1$，已知 $f(a)-p^{a-b}f(b)=f(a-b)$，所以取模等价于不断的 $f(a-kb)$，最终得到 $f(a\bmod b)$。

然后就正常的 $\text{exGcd}$ 没啥大问题，唯一比较麻烦的是有一个 $y=x-y\times\lfloor f(a)/f(b)\rfloor$。

即 $\lfloor a/b\rfloor$ 的求解，可以化为 $(a-a\bmod b)/b$，如果 $f(b)>0$ 的话直接求逆元就没了，主要是 $p^b=1$ 的情况。

考虑直接展开原式，时刻记住 $p^b\equiv 1\pmod {998244353}$，且以下计算都在 $\bmod 998244353$ 下进行。

\[\frac{p^a-p^{a\bmod b}}{p^b-1} \]

\[=p^{a\bmod b}\times \frac{p^{\lfloor a/b\rfloor}\times b}{p^b-1} \]

\[=p^{a\bmod b}\times \frac{p^{\lfloor a/b\rfloor}}{p^b-1} \]

\[=p^{a\bmod b}+p^{a\bmod b+b}+\cdots +p^{a-b} \]

\[=\lfloor a/b\rfloor\times p^{a\bmod b} \]

于是就可以简单计算了。

但是得到的 $x$ 有可能是真正的 $x$，有可能是 $x-(p^b-1)$。

而且 $(a,b,x,y)$ 的 $\text{exGcd}$ 有经典结论 $|x|\leq b,|y|\leq a$，所以如果是后者，只需要简单加上 $p^b-1$。

这个结论可以用归纳法证，它也是把 int 丢进 $\text{exGcd}$ 不会爆 int 的理论基础。

又不难发现 $x,y$ 正负交替，所以根据递归层数就可以判断 $x$ 的正负，于是做完了。

记得特判 $y|x$ 的无解情况。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const LL P = 998244353;

LL p, a, b;

LL read(){
	LL x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? - 1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}

LL Gcd(LL a, LL b) {
	while(b) {LL c = a; a = b, b = c % b;}
	return a; 
}

LL Pow(LL a, LL b, LL p) {
	LL s = 1;
	for(; b; b >>= 1) {
		if(b & 1) s = s * a % p;
		a = a * a % p;
	}
	return s;
}

LL F(LL a) {return (Pow(2, a, P) + P - 1) % P;} 

LL Get(LL a, LL b) {
	LL y = F(b);
	if(! y) return (a / b) * Pow(2, a % b, P) % P;
	return (F(a) - F(a % b) + P) % P * Pow(y, P - 2, P) % P;
}

bool exGcd(LL a, LL b, LL &x, LL &y) {
	if(! b) {x = 1, y = 0; return false;}
	bool o = exGcd(b, a % b, x, y);
	LL z = x; x = y, y = ((z - y * Get(a, b) % P) % P + P) % P;
	return ! o;
}

int main() {
	p = read(), a = read(), b = read();
	if(p > 2 || !(a % b) || Gcd(a, b) != 1) {puts("-1"); return 0;}
	LL x, y;
	bool o = exGcd(a, b, x, y);
	if(o) x = (x + F(b)) % P;
	printf("%lld\n", (x % P + P) % P);
	return 0;
}

$\mathcal B$

给定长度为 $n$ 的数列 $a$ 和目标数列 $b$，其中的数字都在 $[1,m]$ 中，在 $\leq 60000$ 个操作内构造方案将 $a$ 变成 $b$。

一次操作形如 $(p,a_1,a_2,\cdots,a_m)$，表示将数列内从 $p$ 开始的一个 $m$ 的排列重新排成另一个 $m$ 的排列 $a$。

$n\leq 200,m\leq 10$。

有解的充要条件是：一开始两个数列就相等，或对应数字个数一样且其中原本都至少有一个排列。

将需要改变的位置根据在 $b$ 中的位置标记，利用排列不难交换相邻项，根据冒泡排序就可以做到 $O(n^2)$。

看着简单写起来要命，而且重度卡常，最后两个点都是 $67000$，大常数选手老泪纵横（

#include<bits/stdc++.h>
using namespace std;

const int N = 210, M = 6e6 + 10;
int T, n, m, tot, p, q;
int a[N], b[N], s[N];
bool vis[N];
vector<int> sa[N], sb[N];

int read(){
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? - 1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}
struct Ans {int p, a[11];} ans[M];

void Clear() {
	tot = p = q = 0;
	for(int i = 1; i <= n; i ++) {
		a[i] = b[i] = s[i] = vis[i] = 0;
		sa[i].clear();
		sb[i].clear();
	}
}

void Back(int o) {
	if(! o) return;
	while(o --) {
		int v = a[p + m];
		ans[++ tot].p = p;
		ans[tot].a[1] = v;
		int now = 1;
		for(int i = 2; i <= m; i ++) {
			if(now == v) now ++;
			ans[tot].a[i] = now; now ++;
		}
		for(int i = 1; i <= m; i ++)
			a[p + i - 1] = ans[tot].a[i];
		s[p] = s[p + m];
		s[p + m] = 0;
		p ++;
	}
}

void Front(int o) {
	if(! o) return;
	while(o --) {
		int v = a[p - 1];
		ans[++ tot].p = p;
		ans[tot].a[m] = v;
		int now = 1;
		for(int i = 1; i <  m; i ++) {
			if(now == v) now ++;
			ans[tot].a[i] = now; now ++;
		}
		for(int i = 1; i <= m; i ++)
			a[p + i - 1] = ans[tot].a[i];
		s[p + m - 1] = s[p - 1];
		s[p - 1] = 0;
		p --;
	}
}

bool Sorted() {
	bool flag = true;
	for(int i = 1; i < n - m; i ++) if(s[i] > s[i + 1]) {flag = false; break;}
	return flag;
}

void Swap(int x, int y) {
	if(a[x] == a[y]) {swap(s[x], s[y]); return;}
	Front(p - y - 1);
	int v1 = a[x];
	int v2 = a[y];
	int now = 1;
	ans[++ tot].p = p;
	for(int i = 1; i <= m - 2; i ++) {
		while(now == v1 || now == v2) now ++;
		ans[tot].a[i] = now; now ++;
	}
	ans[tot].a[m - 1] = v1;
	ans[tot].a[m] = v2;
	for(int i = 1; i <= m; i ++) a[p + i - 1] = ans[tot].a[i];
	
	now = 1;
	ans[++ tot].p = p - 2;
	for(int i = 3; i <= m; i ++) {
		while(now == v1 || now == v2) now ++;
		ans[tot].a[i] = now; now ++;
	}
	ans[tot].a[1] = v2;
	ans[tot].a[2] = v1;
	for(int i = 1; i <= m; i ++) a[p - 2 + i - 1] = ans[tot].a[i];
	swap(s[x], s[y]);
}

void Swap_(int x, int y) {
	if(a[x] == a[y]) {swap(s[x], s[y]); return;}
	Back(x - m - p);
	int v1 = a[x];
	int v2 = a[y];
	int now = 1;
	ans[++ tot].p = p;
	for(int i = 3; i <= m; i ++) {
		while(now == v1 || now == v2) now ++;
		ans[tot].a[i] = now; now ++;
	}
	ans[tot].a[1] = v1;
	ans[tot].a[2] = v2;
	for(int i = 1; i <= m; i ++) a[p + i - 1] = ans[tot].a[i];
	
	now = 1;
	ans[++ tot].p = p + 2;
	for(int i = 1; i <= m - 2; i ++) {
		while(now == v1 || now == v2) now ++;
		ans[tot].a[i] = now; now ++;
	}
	ans[tot].a[m - 1] = v2;
	ans[tot].a[m] = v1;
	for(int i = 1; i <= m; i ++) a[p + 2 + i - 1] = ans[tot].a[i];
	swap(s[x], s[y]);
}

void Sort() {
	while(! Sorted()) {
		Back(n - m + 1 - p);
		for(int i = n - m - 1; i >= 1; i --)
			if(s[i] > s[i + 1]) Swap(i, i + 1);
		if(Sorted()) break;
		Front(p - 1);
		for(int i = m + 1; i < n; i ++)
			if(s[i] > s[i + 1]) Swap_(i, i + 1);
	}
}

int Get(int a[]) {
	int num[15];
	memset(num, 0, sizeof(num));
	for(int i = 1; i < m; i ++) num[a[i]] ++;
	for(int i = m; i <= n; i ++) {
		num[a[i]] ++;
		num[a[i - m]] --;
		bool flag = true;
		for(int j = 1; j <= m; j ++) if(! num[j]) {flag = false; break;}
		if(flag) return i - m + 1;
	}
	return 0;
}

void Work() {
	n = read(), m = read();
	Clear();
	for(int i = 1; i <= n; i ++) a[i] = read(), sa[a[i]].push_back(i);
	for(int i = 1; i <= n; i ++) b[i] = read(), sb[b[i]].push_back(i);
	for(int i = 1; i <= m; i ++)
		if(sa[i].size() != sb[i].size()) {puts("NO"); return;}
	bool flag = true;
	for(int i = 1; i <= n; i ++) if(a[i] != b[i]) {flag = false; break;}
	if(flag) {puts("YES"); puts("0"); return;}

	p = Get(a), q = Get(b);
	if(! p || ! q) {puts("NO"); return;}
	
	for(int i = 1; i <= m; i ++)
		random_shuffle(sb[i].begin(), sb[i].end());
	
	Back((n - m + 1) - p);
	for(int i = 1; i <= n - m; i ++) {
		int v = a[i];
		for(int j = 0; j < (int) sb[v].size(); j ++) {
			int p = sb[v][j];
			if(vis[p] || (p >= q && p <= q + m - 1)) continue;
			s[i] = p, vis[p] = true; break;
		}
	}
	Sort();

	if(p < q) Back(q - p);
	if(p > q) Front(p - q);
	
	ans[++ tot].p = p;
	for(int i = 1; i <= m; i ++) ans[tot].a[i] = b[q + i - 1];
	
	puts("YES");
	int sum = 0;
	for(int i = 1; i <= tot; i ++) sum += (i == tot || ans[i].p != ans[i + 1].p);
	printf("%d\n", sum);
	for(int i = 1; i <= tot; i ++) if(i == tot || ans[i].p != ans[i + 1].p) {
		printf("%d ", ans[i].p);
		for(int j = 1; j <= m; j ++) printf("%d ", ans[i].a[j]);
		puts("");
	} 
}

int main() {
	int T = read();
	while(T --) Work();
	return 0;
}

$\mathcal C$

给定 $n$ 个节点 $m$ 条边的无向图，每条边有初始权值 $0/1$。

每次可以翻转一条边，同时翻转所有和它有共同端点的边（自己只翻转一次），求构造翻转方案使得所有边都为 $0$。

数据保证有解，$n\leq 1000,m\leq n\times (n-1)/2$。

直接用边异或消元可以得到 50pts 的好成绩，必须考虑把消元扔到点上。

考虑一个点为 $1$ 表示将与它相连的边都翻转，那么一次边的翻转可以视作 $u,v,(u,v)$ 两点一边的翻转。

全部为 $0$ 的充要条件是每个点和与它相连的所有边的异或和为 $0$。

考虑将每个点的这个异或和记为 $E$，能影响到它的点记为 $V$。

对于边 $(u,v)$，显然 $E(u)\to v,E(v)\to u$，然后对于所有度数为偶数的点 $E(u)\to u$。

因为将这个点翻转后，点权与所有相连的边权的异或和必变。（奇度点则必不变）

然后所有 $V$，初始只有 $V(u)\to u$。

然后两个同步消元，得到影响每个点的其他点。

然后根据初始连边情况判断一个点需不需要翻转，要的话就将所有能影响到它的点翻转。

最后把要翻转的点翻转一边就知道了每条边要不要翻转了。

利用 bitset 优化是基本操作了，时间复杂度 $O(n^3/w)$。

#include<bits/stdc++.h>
using namespace std;

const int N = 1010, M = N * N;
int n, m, a[M];
int d[N], d1[N], d2[N];
vector<int> G[N];
bitset<N> E[N], V[N];

int read(){
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? - 1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}

int main() {
	n = read(), m = read();
	for(int i = 1; i <= m; i ++) {
		int u = read(), v = read(); a[i] = read();
		E[u].flip(v);
		E[v].flip(u);
		G[u].push_back(i);
		G[v].push_back(i);
		if(a[i])
			d1[u] ^= 1, d1[v] ^= 1;
		d[u] ^= 1, d[v] ^= 1;
	}
	for(int i = 1; i <= n; i ++) {
		if(! d[i]) E[i].flip(i);
		V[i].flip(i);
	}
	for(int i = 1; i <= n; i ++) {
		int k = 0;
		for(int j = i; j <= n; j ++) if(E[j][i]) {k = j; break;}
		if(! k) continue;
		swap(E[k], E[i]);
		swap(V[k], V[i]);
		for(int j = 1; j <= n; j ++) if(j != i && E[j][i]) E[j] ^= E[i], V[j] ^= V[i];
	}
	for(int i = 1; i <= n; i ++) if(d1[i])
		for(int j = 1; j <= n; j ++) if(V[i][j]) d2[j] ^= 1;
	for(int i = 1; i <= n; i ++) if(d2[i])
		for(int u : G[i]) a[u] ^= 1;
	int tot = 0;
	for(int i = 1; i <= m; i ++) if(a[i]) tot ++;
	printf("%d\n", tot);
	for(int i = 1; i <= m; i ++) if(a[i]) printf("%d ", i); puts("");
	return 0;
}

$$\mathcal{NOIP2021\ RP++}$$

码农公寓

一场 NOIP 模拟赛

\(\mathcal A\)

\(\mathcal B\)

\(\mathcal C\)

$$\mathcal{NOIP2021\ RP++}$$

码农公寓

\(\mathcal A\)

\(\mathcal B\)

\(\mathcal C\)

$$\mathcal{NOIP2021\ RP++}$$

相关文章