Difference between revisions of "BreakFast:The 15th Chinese Northeast Collegiate Programming Contest"

2,201 bytes added , 23:52, 20 July 2021

m

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

BreakFast

Bureaucrats, Interface administrators, Administrators

201

edits

@@ Line 1: / Line 1: @@
 __TOC__
+== Replay ==
 先放个比赛链接：[https://codeforces.com/gym/103145 The 15th Chinese Northeast Collegiate Programming Contest]
@@ Line 51: / Line 53: @@
 lhr：哦，不能选，那还不对。。。
 </blockquote>
-一万年后，我问谁说不能选空集来着？？（打扰了，好像是我
+一万年后，我问谁TM说不能选空集来着？？（打扰了，好像是我
 蓝总按着推出来的dp式写，一发'''<font color="green">AC</font>'''！
@@ Line 83: / 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？！
-[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>？？？？？？？？？？？？
-[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>'''了！
 == Problem A ==
-solved by
+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>
+数学对称妙啊

Difference between revisions of "BreakFast:The 15th Chinese Northeast Collegiate Programming Contest"

BreakFast:The 15th Chinese Northeast Collegiate Programming Contest (view source)

Revision as of 23:52, 20 July 2021