首页 > 其他分享 >LY1156 [ 20230320 CQYC省选模拟赛 T3 ] 集结

LY1156 [ 20230320 CQYC省选模拟赛 T3 ] 集结

时间:2024-03-04 10:45:07浏览次数:31  
标签:include LY1156 20230320 省选 int ans mod flg define

题意

平面上 \(n\) 个点,每个点按照曼哈顿距离移动。

要求在 \(m\) 时刻后,所有点都处于同一位置。

求方案数。

Sol

平凡地,考虑曼哈顿距离转切比雪夫距离。

这样 \(x\) 和 \(y\) 就完全独立了。

考虑先算 \(x\) 的贡献,再算 \(y\) 的贡献。

判断一下是否能到当前的 \(x\) 或 \(y\) 就做完了。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#define ll long long
#define pii pair <int, int>
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
#define fi first
#define se second

const int N = 1e3 + 5, M = 1e5 + 5, mod = 998244353;

int pow_(int x, int k, int p) {
	int ans = 1;
	while (k) {
		if (k & 1) ans = 1ll * ans * x % p;
		x = 1ll * x * x % p;
		k >>= 1;
	}
	return ans;
}

array <int, M> fac, inv;

void init(int n = 1e5 + 2) {
	fac[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[n] = pow_(fac[n], mod - 2, mod);
	for (int i = n; i; i--)
		inv[i - 1] = 1ll * inv[i] * i % mod;
}

int C(int n, int m) {
	if (n < m) return 0;
	return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}

array <pii, N> qrl;

void Mod(int &x) {
	if (x >= mod) x -= mod;
	if (x < 0) x += mod;
}

signed main() {
	/* freopen("assemble.in", "r", stdin); */
	/* freopen("assemble.out", "w", stdout); */
	int n = read(), m = read();
	for (int i = 1, x, y; i <= n; i++)
		x = read(), y = read(), qrl[i] = make_pair(x + y, x - y);
	init();
	sort(qrl.begin() + 1, qrl.begin() + 1 + n);
	int tp0 = 0, tp1 = 0;
	for (int i = qrl[1].fi - m; i <= qrl[n].fi + m; i++) {
		bool flg = 0;
		for (int j = 1; j <= n; j++)
			if (abs(qrl[j].fi - i) > m || ((m - abs(qrl[j].fi - i)) & 1))
				flg = 1;
		if (flg) continue;
		int sum = 1;
		for (int j = 1; j <= n; j++)
			sum = 1ll * sum * C(m, (m - abs(qrl[j].fi - i)) / 2) % mod;
		tp0 += sum, Mod(tp0);
	}
	sort(qrl.begin() + 1, qrl.begin() + 1 + n, [](pii x, pii y) {
		return x.se < y.se;
	});
	for (int i = qrl[1].se - m; i <= qrl[n].se + m; i++) {
		bool flg = 0;
		for (int j = 1; j <= n; j++)
			if (abs(qrl[j].se - i) > m || ((m - abs(qrl[j].se - i)) & 1))
				flg = 1;
		if (flg) continue;
		int sum = 1;
		for (int j = 1; j <= n; j++)
			sum = 1ll * sum * C(m, (m - abs(qrl[j].se - i)) / 2) % mod;
		tp1 += sum, Mod(tp1);
	}
	write(1ll * tp0 * tp1 % mod), puts("");
	return 0;
}

标签:include,LY1156,20230320,省选,int,ans,mod,flg,define
From: https://www.cnblogs.com/cxqghzj/p/18051330

相关文章

  • 联合省选2024游记/退役记
    等到风吹过树梢,等到蝴蝶扇动翅膀,等到鹿在林间漫步,等到鲸吞吐海洋。等到历尽千帆,我们再次相逢。Day-4做了一个梦。梦中的自己出现在跑道上,一声哨响过后,奋力向前奔跑。但胸口仿佛负千斤,被压得胸闷,被挤得气短,逐渐远远落于众人身后。醒来时才发觉,胸口的大石,是需要自己移除的......
  • 爆零记——2024省选篇
    这是我短暂的不到半年的OI生涯中第一次爆零。不过我知道这绝对不会是最后一次的:)\[Day\;-1\]瞄了一眼各种板子,唯独没看数论。\[Day\;1\]上来先看了一眼题目,觉得T1T2是可做题。觉得T1简单,先写T1。然后写了将近两个半小时之后发现自己看错题了……题目:\[\sum_{i=0}^{m-1}(......
  • NOI2023联合省选 HE省选体验
    写在前面照了挺多照片,本来只想传照片不写文字的,但博客园只让传小于等于2MB的照片(这大小是个手机照的照片都传不上去吧),那好吧,我就写写;Day0出发时还是很激动的,但没有CSP和NOIP那么紧张(那两篇等以后看看再写吧);熟悉的大巴,熟悉的路线(毕竟也是第三次了),确实勾起了很多回忆;大巴上没......
  • noi省选体验赛游记
    3.1上午早上吃完饭先拿了手机然后上了节奥赛课,十点左右我们就出发了,先坐大巴到德州,中午自己安排吃饭,我,w1210,cpa,zhengchenxi坐一起吃的巴拉永和,盖饭+虾饺+蒸饺,吃完自己坐高铁到秦皇岛,然和我们集合又坐大巴去住了高档的首旅京伦(晚上打车出去转,司机说你们是学生吧,怎么还住上首旅京伦......
  • NOI2024联合省选 游寄
    day-62024/2/24元宵节下午去黄河北玩的路上发现没进NOIP的可以去省选锻炼,而且就在zzc的捞胆位——山师附中,就填了报名表交了上去,期待CCF能让我去。day02024/3/1等了一周,中午终于下通知了,但选Windows的被发配到山师二附中了。激动得很。晚上5:15从学校窜了出来,......
  • 省选?
    ......
  • 省选日寄
    省选的前几天莫名有些害怕,听别人说要带枕头和睡袋。day0晚上放学回家,为了早上多睡会精神饱满,在开发区订了酒店,晚上恶补了考试机器操作流程。(感谢yxcat提供的“指北”)晚上狼狈地背着板子。day1早上六点半醒的,吃饭,去考场拿到了准考证。当然,第一天的考试非常劲爆。打开机器以后......
  • [省选联考 2024] 魔法手杖
    退役三年选手回来做了下~这题直观感觉很吓人,其实看到异或就可以往Trie树上思考了。这题有两个未知量\(S\)和\(x\),其中\(S\subseteq[n]\),\(x\in[0,2^k)\cap\Z\),状态过于复杂,肯定不能枚举,从答案的角度考虑。首先直观感受是有点像二分,其实我们可以从高位往低位确定答案\(ans......
  • 考完省选神志不清写的考场技巧
    原本写在文本文档里的,懒得改,就发纯文字了写作思路混乱,想到什么写什么 总:先想正解再想部分再冲正解再打暴力再打部分再乱搞随机化:平面随机旋转、随机排序随机游走,序列随机排序随机染色分组,随机染色异或哈希想不出来考虑图论建模,万一图论秒了?时空卡瓶颈了?考虑......
  • 2024省选游记
    day\(-N\)(\(N\in\real\))day-1大家都喜欢day0板子练习,早晨起床回市区,拖了会儿。写了SAM,KMP,EXKMP,线段树合并,Matrixtree,Splay,tarjan,FST,调LCT时发现手感不佳。开了一把鳊鱼八十镜牢,三破剑箱强度真的幽默。最后放弃了LCT复习了一些算法,吹水,睡觉。day1最唐的一......