Codeforces Round #439 (Div. 2) 题解

题目链接 Round 439 div2

就做了两道题TAT

开场看C题就不会

然后想了好久才想到。

三种颜色挑出两种算方案数其实是独立的，于是就可以乘起来了。

E题想了一会有了思路，然后YY出了一种方案。

我们可以对每个矩形随机一个权值，然后用二维树状数组搞下。

询问的时候看两个点权值是否相等就可以了

于是就过了。

D题待补

给出一棵完全二叉树，这棵树上有附带的m条边（m <= 4），求这张图的简单路径条数。

qls的题就是厉害……

C题

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define MP		make_pair

#define fi		first

#define se		second

typedef long long LL;

const int N = 5010;

const int mod = 998244353;

int P[N][N], C[N][N];

int a, b, c;

int calc(int x, int y){

	if (x > y) swap(x, y);

	LL ret = 0;

	rep(i, 0, x) ret = (ret + 1ll * P[y][i] * C[x][i]) % mod;

	return ret;

}

int main(){

	C[0][0] = P[0][0] = 1;

	scanf("%d%d%d", &a, &b, &c);

	rep(i, 1, 5000){

		C[i][0] = P[i][0] = 1;

		rep(j, 1, i){

			P[i][j] = (1ll * P[i - 1][j - 1] * j % mod + 1ll * P[i - 1][j] % mod) % mod;

			C[i][j] = (1ll * C[i - 1][j - 1] + 1ll * C[i - 1][j]) % mod;

		}

	}

	int ans = 1ll * calc(a, b) % mod * 1ll * calc(b, c) % mod * 1ll * calc(a, c) % mod;

	printf("%d\n", ans);

	return 0;

}

E题

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define MP		make_pair

typedef long long LL;

typedef pair <int, int> PII;

const LL mod = 1e9 + 7;

const int N = 5010;

map <PII, LL> mp;

int cnt = 0;

int n, m, q;

int p[N][N];

LL c[N][N];

inline void add(int x, int y, LL val){

	for (; x <= n; x += x & -x){

		for (int t = y; t <= m; t += t & -t){

			c[x][t] = (c[x][t] + val) % mod;

			c[x][t] = (c[x][t] + mod) % mod;

		}

	}

}

inline LL query(int x, int y){

	LL ret = 0;

	for (; x ; x -= x & -x){

		for (int t = y; t ; t -= t & -t){

			(ret += c[x][t]) %= mod;

		}

	}

	return ret;

}

inline LL solve(int x, int y){

	LL ret = query(x, y) % mod;

	return ret;

}

int main(){

	scanf("%d%d%d", &n, &m, &q);

	rep(i, 1, n) rep(j, 1, m) p[i][j] = ++cnt;

	rep(i, 1, q){

		int op;

		scanf("%d", &op);

		if (op == 1){

			int x1, y1, x2, y2;

			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

			if (x1 > x2) swap(x1, x2);

			if (y1 > y2) swap(y1, y2);

			LL cnt = (LL)rand() * (LL)rand() * (LL)rand() % mod;

			mp[MP(p[x1][y1], p[x2][y2])] = cnt;

			add(x1, y1, cnt);

			add(x1, y2 + 1, -cnt);

			add(x2 + 1, y1, -cnt);

			add(x2 + 1, y2 + 1, cnt);

		}

		else if (op == 2){

			int x1, y1, x2, y2;

			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

			if (x1 > x2) swap(x1, x2);

			if (y1 > y2) swap(y1, y2);

			LL cnt = mp[MP(p[x1][y1], p[x2][y2])];

			add(x1, y1, -cnt);

			add(x1, y2 + 1, cnt);

			add(x2 + 1, y1, cnt);

			add(x2 + 1, y2 + 1, -cnt);

		}

		else{

			int x1, y1, x2, y2;

			scanf("%d%d%d%d", &x1, &y1, &x2, &y2);

			LL xx = solve(x1, y1);

			LL yy = solve(x2, y2);

			if (xx == yy) puts("Yes");

			else puts("No");

		}

	}

	return 0;

}

巴特西

Codeforces Round #439 (Div. 2) 题解

最新文章

热门文章