codevs#6 题解

你会奇怪我怎么会打这种比赛？

我的回答非常简单也符合逻辑：

那是因为我就是NOIP-选手啊。

当然并不是现场打的。

A。

题目大意：

给定$0\leq{x}<10^n$，求$0\leq{y}<10^n$使得$py\equiv{x}\pmod{10^n}$，其中$p$表示233...333（共$n-1$个3）。

数据范围$n\leq{10^6}$。

题解：

首先逆元显然存在。

但是显然利用拓展欧几里得是不行的。因为我懒得写高精度啊。

我们考虑乘法，设答案为$y$，其实就是一堆$3y$和最后的一个$2y$错位相加。

那么我们可以不断地求出$3y$每一位是什么。

然后再除以三就知道$y$是什么了。

详细来看的话参考代码吧。

时间复杂度$O(n)$。

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
#define N 1000010
char s[N];
int ans[N];

int n;
void check(int x) {
	ll sum = 3 * x % 10, up = 0, temp;
	ans[n] = s[n] - '0';
	for (int i = n - 1; i >= 1; --i) {
		if (i == 1)
			sum = sum - 3 * x % 10 + 2 * x % 10;
		temp = sum + up;
		if(temp % 10 <= s[i] - '0')
			ans[i] = (s[i] - '0') - temp % 10;
		else
			ans[i] = (s[i] - '0') + 10 - temp % 10;
		temp += ans[i];
		sum += ans[i];
		up = temp / 10;
	}
	//printf("%I64d %I64d %I64d\n", temp, sum, up);
}

int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	
	for (int i = 0; i < 10; ++i)
		if (3 * i % 10 == s[n] - '0')
			check(i);
		
	int sum = 0;
	for (int i = 1; i <= n; ++i)
		sum += ans[i];
	
	ans[0] = (3 - sum % 3) % 3;
	
	int t = 0;
	for(int i = 0; i <= n; ++i) {
		t = t * 10 + ans[i];
		ans[i] = t / 3;
		t %= 3;
	}
	
	for(int i = 1; i <= n; ++i)
		printf("%01d", ans[i]);
	
	return 0;
}

B。

题目大意：

给定$n$个元素，求从这$n$个元素中选出$k$的倍数个数的方案数对$p$取模的余数。

数据范围$n\leq{10^9},k\leq{20}$。

题解：

直接令$f_{i,j}$表示在$i$个元素中选出对$k$取模余数是$j$的个数的方案数。

接着利用矩阵乘法优化DP。

时间复杂度$O(k^3logn)$。

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
int n, m, p;
struct Matrix {
	int w, h, d[50][50];
	Matrix(int _w, int _h) : w(_w), h(_h) {
		memset(d, 0, sizeof d);
	}
	void operator *= (const Matrix &B) {
		Matrix C(w, B.h);
		for (int i = 0; i < C.w; ++i)
			for (int j = 0; j < C.h; ++j)
				for (int k = 0; k < h; ++k)
					C.d[i][j] = ((ll)C.d[i][j] + (ll)d[i][k] * B.d[k][j]) % p;
		*this = C;
	}
};

int main() {
	cin >> n >> m >> p;
	Matrix add(m, m);
	int i, j, k;
	for (i = 0; i < m; ++i) {
		++add.d[i][i];
		++add.d[i][(i + 1) % m];
	}
	
	Matrix ans(1, m);
	ans.d[0][0] = 1;
	
	int y = n;
	for (; y; y >>= 1, add *= add)
		if (y & 1)
			ans *= add;
	
	printf("%d", (ans.d[0][0] + p - 1) % p);
	
	return 0;
}

C。

题目大意：

给定平面上的$n$条直线，$m$次操作，每次给定一个信息$(t,i,j)$，意思是第$i$条直线和第$j$条直线平行或是垂直。

对于这条信息，如果和之前输入的信息产生冲突则输出$-1$，否则分别输出在当前的信息下平面上所有直线的交点数最多和最少能有多少。

题解：

用带权并查集维护直线之间的位置关系。

对于每个连通分量记录有多少直线和根平行、垂直，不妨分别记为$a,b$。

交点数最多的话，可以认为每个连通分量里面的所有直线和剩下的所有连通分量中的所有直线均相交，于是贡献是$2\times{a}\times{b}+(a+b)\times{(n-a-b)}$。当然最后需要除2。

要想交点数最少，那么就相当于所有直线都在一个连通分量中。于是答案为$\sum{x}\times{\sum{y}}$。其中$x=a,y=b$或者$x=b,y=a$。

根据贪心，我们令所有连通分量中的$x\leq{y}$就能得出最小的交点数。证明自己想吧。

于是在操作中动态维护这两个答案就行了。

注意下标需要离散化。时间复杂度$O(mlogn)$。

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

int getc() {
	static const int L = 1 << 15;
	static char buf[L], *S = buf, *T = buf;
	if (S == T) {
		T = (S = buf) + fread(buf, 1, L, stdin);
		if (S == T)
			return EOF;
	}
	return *S++;
}

int getint() {
	int c;
	while (!isdigit(c = getc()));
	int x = c - '0';
	while (isdigit(c = getc()))
		x = (x << 1) + (x << 3) + c - '0';
	return x;
}

map<int, int> M;

#define N 200010
int fa[N], siz[N], d[N], p[N], q[N], id;
int check(int x) {
	if(M[x] == 0) {
		++id;
		fa[id] = id;
		siz[id] = 1;
		d[id] = 0;
		p[id] = 1;
		q[id] = 0;
		return M[x] = id;
	}
	else
		return M[x];
}

int find(int x) {
	if (x == fa[x])
		return x;
	int temp = fa[x];
	fa[x] = find(fa[x]);
	d[x] ^= d[temp];
	return fa[x];
}

typedef long long ll;
int main() {
	int n = getint(), m = getint();
	ll ans = (ll)n * (n - 1);
	int t, x, y, i, j, rx, ry, tp, tq, sum_mn = 0, sum_mx = n;
	for (i = 1; i <= m; ++i) {
		t = getint();
		x = check(getint());
		y = check(getint());
		rx = find(x);
		ry = find(y);
		if (rx == ry) {
			if (t == (d[x] ^ d[y]))
				printf("%lld %lld\n", ans >> 1, (ll)sum_mn * sum_mx);
			else
				puts("-1");
		}
		else {
			if (siz[rx] > siz[ry]) {
				swap(x, y);
				swap(rx, ry);
			}
			
			ans -= (ll)p[rx] * q[rx] * 2 + (ll)siz[rx] * (n - siz[rx]);
			ans -= (ll)p[ry] * q[ry] * 2 + (ll)siz[ry] * (n - siz[ry]);
			
			siz[ry] += siz[rx];
			fa[rx] = ry;
			d[rx] = d[x] ^ d[y] ^ t;
			
			if (d[rx] == 0) {
				tp = p[ry] + p[rx];
				tq = q[ry] + q[rx];
			}
			else {
				tp = p[ry] + q[rx];
				tq = q[ry] + p[rx];
			}
	
			sum_mn -= min(p[rx], q[rx]) + min(p[ry], q[ry]);
			sum_mx -= max(p[rx], q[rx]) + max(p[ry], q[ry]);
			
			p[ry] = tp;
			q[ry] = tq;
			sum_mn += min(tp, tq);
			sum_mx += max(tp, tq);
			
			ans += (ll)p[ry] * q[ry] * 2 + (ll)siz[ry] * (n - siz[ry]);
			printf("%lld %lld\n", ans >> 1, (ll)sum_mn * sum_mx);
		}
	}
	
	return 0;
}