BreakFast:The 15th Chinese Northeast Collegiate Programming Contest - Revision history

BreakFast: Protected "BreakFast:The 15th Chinese Northeast Collegiate Programming Contest" ([Edit=Protect from non-authors] (indefinite))

2021-07-20T15:52:31Z

Protected "BreakFast:The 15th Chinese Northeast Collegiate Programming Contest" ([Edit=Protect from non-authors] (indefinite))

← Older revision	Revision as of 15:52, 20 July 2021
(No difference)

BreakFast: /* Problem A */

2021-06-23T12:43:39Z

Problem A

← Older revision		Revision as of 12:43, 23 June 2021
Line 97:		Line 97:

	推公式 <math> ... </math>		推公式 <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 ==		== Problem B ==

BreakFast at 15:33, 20 June 2021

2021-06-20T15:33:13Z

← Older revision		Revision as of 15:33, 20 June 2021
Line 103:		Line 103:
	== lzwの总结 ==		== lzwの总结 ==

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

	感觉省赛好多sb题啊		感觉省赛好多sb题啊

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

	数学对称妙啊		数学对称妙啊

BreakFast: add lzw's point

2021-06-20T15:24:26Z

add lzw's point

← Older revision		Revision as of 15:24, 20 June 2021
Line 94:		Line 94:

	== Problem A ==		== Problem A ==
	solved by		solved by lhr & wx

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

			== Problem B ==


			== lzwの总结 ==

			太妙了，<math> 2^1</math> 居然等于2

			感觉省赛好多sb题啊

			我想了啥？这场我在干啥？感觉成了无情的敲键盘机器

			数学对称妙啊

BreakFast: /* Replay */

2021-06-20T13:09:05Z

Replay

← Older revision		Revision as of 13:09, 20 June 2021
Line 53:		Line 53:
	lhr：哦，不能选，那还不对。。。		lhr：哦，不能选，那还不对。。。
	</blockquote>		</blockquote>
	~~一万年后，我问谁说不能选空集来着？？（打扰了，好像是我~~		一万年后，我问谁TM说不能选空集来着？？（打扰了，好像是我

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

BreakFast: /* Replay */

2021-06-20T09:57:37Z

Replay

← Older revision		Revision as of 09:57, 20 June 2021
Line 85:		Line 85:
	提交！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？！		提交！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://imgtu.com/i/RFBrvQ [[File:~~https://z3.ax1x.com/2021/06/20/RFBrvQ.jpg~~\|fig:]]]~~		https://z3.ax1x.com/2021/06/20/RFBrvQ.jpg

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

	~~[https://imgtu.com/i/RFBIv4 [[File:~~https://z3.ax1x.com/2021/06/20/~~RFBIv4~~.png~~\|fig:]]]~~		https://z3.ax1x.com/2021/06/20/RFs6DH.png

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

BreakFast at 09:48, 20 June 2021

2021-06-20T09:48:21Z

← Older revision		Revision as of 09:48, 20 June 2021
Line 1:		Line 1:
	__TOC__		__TOC__

			== Replay ==

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

BreakFast: /* Replay */

2021-06-20T09:46:38Z

Replay

← Older revision		Revision as of 09:46, 20 June 2021
Line 1:		Line 1:
	__TOC__		__TOC__

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

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


	正文开始：		正文开始：

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

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

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

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

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

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

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

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

	然后我去看C题，蓝总和欣姐去写A的暴力。		然后我去看C题，蓝总和欣姐去写A的暴力。
Line 30:		Line 29:
	让我手摸一下样例，嗯，果然不对~~		让我手摸一下样例，嗯，果然不对~~

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

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

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

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

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

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

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

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

			lhr：首先是空集

			lzw：可以选空集？

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

			蓝总按着推出来的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://imgtu.com/i/RFBrvQ [[File:https://z3.ax1x.com/2021/06/20/RFBrvQ.jpg\|fig:]]]

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

			[https://imgtu.com/i/RFBIv4 [[File:https://z3.ax1x.com/2021/06/20/RFBIv4.png\|fig:]]]

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

	== Problem A ==		== Problem A ==
	solved by		solved by

BreakFast: /* Replay */

2021-06-20T09:08:41Z

Replay

← Older revision		Revision as of 09:08, 20 June 2021
Line 38:		Line 38:
	又过了几年，我推了个新的dp式跟欣姐讲了讲。其中，欣姐一句话让我觉悟了~~		又过了几年，我推了个新的dp式跟欣姐讲了讲。其中，欣姐一句话让我觉悟了~~

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

	== Problem A ==		== Problem A ==
	solved by		solved by

BreakFast: /* Replay */

2021-06-20T09:08:16Z

Replay

← Older revision		Revision as of 09:08, 20 June 2021
Line 8:		Line 8:
	正文开始：		正文开始：

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

	M是阅读理解题（拼音转双拼，表示从来没用过双拼啊），蓝总跟我讲清题意就去写了，随后我抓去做苦力。		M是阅读理解题（拼音转双拼，表示从来没用过双拼啊），蓝总跟我讲清题意就去写了，随后我抓去做苦力。
Line 20:		Line 20:
	跟蓝总互通了一下思路后，蓝总去写K，我去找E的规律。		跟蓝总互通了一下思路后，蓝总去写K，我去找E的规律。

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

	等我吃饭回来，不出我所料蓝总又<strike>AK</strike> <font color="green"><b>AC</b></font>了！		等我吃饭回来，不出我所料蓝总又<strike>AK</strike> <font color="green"><b>AC</b></font>了！
Line 34:		Line 34:
	我越想越不对劲“容斥？好熟悉啊，在哪里做过来着？哦~ 西安邀请赛被卡了3h的F题！”		我越想越不对劲“容斥？好熟悉啊，在哪里做过来着？哦~ 西安邀请赛被卡了3h的F题！”

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

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

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

	== Problem A ==		== Problem A ==
	solved by		solved by