BreakFast:The 15th Chinese Northeast Collegiate Programming Contest

Replay

先放个比赛链接：The 15th Chinese Northeast Collegiate Programming Contest

正文开始：

I语法题，蓝总开场10min后一发 AC。

M是阅读理解题（拼音转双拼，表示从来没用过双拼啊），蓝总跟我讲清题意就去写了，随后我抓去做苦力。

回来后蓝总已经 AK AC了！

再之后我和蓝总去看E题，嗯？不会，下一题~~

读完K题我就产生了强烈的生理反应，直呼这不就是离线排序算贡献的经典SB题？

跟蓝总互通了一下思路后，蓝总去写K，我去找E的规律。

蓝总AC K之后，欣姐到达战场，我跟蓝总说了一下E的规律（“ ${\textstyle 6p}$ 一定可以构造出来”，就去吃饭惹。

等我吃饭回来，不出我所料蓝总又AK AC了！

然后我去看C题，蓝总和欣姐去写A的暴力。

过了一会，我给蓝总讲了讲C的dp转移式，嗯，听起来很有道理~~

让我手摸一下样例，嗯，果然不对~~

几年后，欣姐跟我们讲了讲A的思路，这里需要容斥啦，~~我嘴上说着很有道理，其实根本没听懂（欣姐应该不会看吧？）~~

我越想越不对劲“容斥？好熟悉啊，在哪里做过来着？哦~ 西安邀请赛被卡了3h的F题！”

哈！正难则反！我讲了讲思路并写下一个神奇的柿子，手摸也对，蓝总一发AC！

又过了几年，我推了个新的dp式跟欣姐讲了讲。其中，欣姐一句话让我觉悟了~~

我继续推C，蓝总和欣姐去抄 J 的模板，抄完后，嗯？怎么又不对，遂放弃 J

又过了几年，我掏出最新的dp转移式跟蓝总讲（蓝总貌似不相信的样子并回赠了一个样例，于是发生了下面的对话

lhr：答案是 ${\textstyle 4}$ 啊
lzw：哪 ${\textstyle 4}$ 种？
lhr：首先是空集
lzw：可以选空集？
lhr：哦，不能选，那还不对。。。

一万年后，我问谁TM说不能选空集来着？？（打扰了，好像是我

蓝总按着推出来的dp式写，一发AC！

我们三个一起来看 J，发现是弧度制跟角度值弄混了。。。

改完后测样例，哦~！输出的 ${\textstyle x}$ 和 ${\textstyle y}$ 都是对的， ${\textstyle z}$ 差很多，怎么肥四？

接下来是最具有戏剧性的一幕（难以用语言描述）

lhr：诶，jls模板的这个公式不对称啊，计算 ${\textstyle x}$ 的时候是 ${\textstyle xz}$ ，计算 ${\textstyle y}$ 的时候是 ${\textstyle yz}$ ，怎么计算 ${\textstyle z}$ 的时候成了 ${\textstyle xx}$ ？
三人大惊！
lhr：改成 ${\textstyle zz}$ 试试？
艹，样例过了！
lhr：交一发试试？
AC了！

原来这就是现场改板子吗？学到了学到了

这时距离比赛结束还剩 ${\textstyle 40}$ min，我们去看 D 题

想了想跟区间开根号那题差不多，蓝总上机去写了

经过蓝总精细的coding手法和扎实的数理基础顺利通过了样例

提交！Submitted ${\textstyle \rightarrow }$ Running on test 1 ${\textstyle \rightarrow }$ Running on test 2 ${\textstyle \rightarrow }$ Wrong Answer on test 2？！

比赛结束 ${\textstyle 4}$ min后发现初始化时居然写成了 ${\textstyle 2^{1}=1}$ ？？？？？？？？？？？？

改过来，提交，AC了！

Problem A

solved by lhr & wx

推公式 $...$

钦定每个数为当前行的最小值，答案为 $nn!(n^{2}-n)!\sum _{i=1}^{n}{\tbinom {n^{2}-i}{n-1}}$

code by lzw.

/*************************************************************************
    > File Name: a.cpp
    > Author: ghost_lzw
    > Mail: lanzongwei@gmail.com 
    > Created Time: Sat Jun 19 19:47:20 2021
 ************************************************************************/

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

using ll=long long;
#define seg(x) x.begin(), x.end()
#define endl '\n'
const int inf = 0x3f3f3f3f, mod = 119 << 23 | 1, Ma = 3e7;

ll inv(ll x, ll b = mod - 2) {
	ll s = 1;
	for (x %= mod; b; b >>= 1, x = x * x % mod)
		if (b & 1) s = s * x % mod;
	return s;
}

struct Mint {
	ll x;
	ll norm(ll x) {
		if (x < 0) x %= mod, x += mod;
		x %= mod;
		return x;
	}
	Mint() {x = 0;}
	Mint(ll x) {
		this->x = norm(x);
	}
	Mint operator + (const Mint& b) {
		return x + b.x;
	}
	Mint operator - (const Mint& b) {
		return x - b.x;
	}
	Mint operator * (const Mint& b) {
		return x * b.x;
	}
	Mint operator / (const Mint& b) {
		return x * inv(b.x);
	}
	Mint& operator = (const ll& x) {
		this->x = norm(x);
		return *this;
	}
};

Mint inv(Mint x) {
	return Mint(inv(x.x));
}

Mint fac[Ma], ifac[Ma];

Mint C(int n, int m) {
	if (m < 0 or m > n) return 0;
	return fac[n] * ifac[m] * ifac[n - m];
}

void solve() {
	int n; cin >> n;
	Mint ans;
	for (int i = 1; i <= n; i++) {
		ans = ans + C(n * n - i, n - 1);
	}
	ans = ans * n * fac[n] * fac[n * n - n];
	cout << ans.x << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	fac[0] = fac[1] = 1;
	ifac[0] = ifac[1] = 1;
	for (int i = 2; i < Ma; i++) fac[i] = fac[i - 1] * i;
	ifac[Ma - 1] = inv(fac[Ma - 1]);
	for (int i = Ma - 2; i > 1; i--)
		ifac[i] = ifac[i + 1] * (i + 1);
	int T; cin >> T;
	while (T--) solve();
	
	return 0;
}

Problem B

lzwの总结

太妙了， $2^{1}$ 居然等于2，lzw数理基础++

感觉省赛好多sb题啊

我想了啥？感觉成了无情的敲键盘机器，还敲错了好多键，希望能再参加打字比赛~~( 希望正式赛队友能让我多练练打字技巧~~

数学对称妙啊

BreakFast:The 15th Chinese Northeast Collegiate Programming Contest

Contents

Replay

Problem A

Problem B

lzwの总结

Navigation menu

Search