View source for BreakFast:The 15th Chinese Northeast Collegiate Programming Contest

__TOC__

== Replay ==

先放个比赛链接：[https://codeforces.com/gym/103145 The 15th Chinese Northeast Collegiate Programming Contest]



正文开始：

I语法题，蓝总开场10min后一发 '''<font color="green">AC</font>'''。

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

回来后蓝总已经 <s>AK</s> '''<font color="green">AC</font>'''了！

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

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

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

蓝总'''<font color="green">AC</font>''' K之后，欣姐到达战场，我跟蓝总说了一下E的规律（“<math display="inline">6p</math> 一定可以构造出来”，就去吃饭惹。

等我吃饭回来，不出我所料蓝总又<s>AK</s> '''<font color="green">AC</font>'''了！

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

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

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

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

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

哈！正难则反！我讲了讲思路并写下一个神奇的柿子，手摸也对，蓝总一发'''<font color="green">AC</font>'''！

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

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

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

<blockquote>lhr：答案是 <math display="inline">4</math> 啊

lzw：哪 <math display="inline">4</math> 种？

lhr：首先是空集

lzw：可以选空集？

lhr：哦，不能选，那还不对。。。
</blockquote>
一万年后，我问谁TM说不能选空集来着？？（打扰了，好像是我

蓝总按着推出来的dp式写，一发'''<font color="green">AC</font>'''！

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

改完后测样例，哦~！输出的 <math display="inline">x</math> 和 <math display="inline">y</math> 都是对的，<math display="inline">z</math> 差很多，怎么肥四？

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

<blockquote>lhr：诶，jls模板的这个公式不对称啊，计算 <math display="inline">x</math> 的时候是 <math display="inline">xz</math>，计算 <math display="inline">y</math> 的时候是 <math display="inline">yz</math>，怎么计算 <math display="inline">z</math> 的时候成了 <math display="inline">xx</math>？

三人大惊！

lhr：改成 <math display="inline">zz</math> 试试？

艹，样例过了！

lhr：交一发试试？

'''<font color="green">AC</font>'''了！
</blockquote>
原来这就是现场改板子吗？学到了学到了

这时距离比赛结束还剩 <math display="inline">40</math> min，我们去看 D 题

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

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

提交！Submitted <math display="inline">\rightarrow</math> Running on test 1 <math display="inline">\rightarrow</math> Running on test 2 <math display="inline">\rightarrow</math> Wrong Answer on test 2？！

https://z3.ax1x.com/2021/06/20/RFBrvQ.jpg

比赛结束 <math display="inline">4</math> min后发现初始化时居然写成了 <math display="inline">2^1 = 1</math>？？？？？？？？？？？？

https://z3.ax1x.com/2021/06/20/RFs6DH.png

改过来，提交，'''<font color="red">AC</font>'''了！

== Problem A ==
solved by lhr & wx

推公式 <math> ... </math>

钦定每个数为当前行的最小值，答案为 <math> n n! (n^2 - n)!  \sum_{i=1}^{n}{\tbinom{n^2 - i}{n - 1}} </math>

code by lzw.

<syntaxhighlight lang="cpp">
/*************************************************************************
    > 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;
}
</syntaxhighlight>

== Problem B ==


== lzwの总结 ==

太妙了，<math> 2^1</math> 居然等于2，lzw数理基础++

感觉省赛好多sb题啊

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

数学对称妙啊