ZJOI2019 Day1 补题小记

Vexoben

Apr 11, 2019

It takes 35 minutes to read this article.

一试挂惨了呢……因为不知道自己在干什么，游记也就免了吧。

考场debuff太重是一个原因，基本功不够硬也是无法否定的。

争取二试前把题补完吧。

（刷新以获取数学公式）

麻将

在平生第一场大赛中做到了地主斗，第二场大赛中做到了麻将。都是一样的不会。

场上打了个 $20$ 分暴力就跑路了。不过听说状压和特殊性质点也能搞到很多分。

不过这分显然是给后面题的分都拿得差不多的人做的吧。

如果求出一个 $f_i$ 表示已经摸了 $i$ 张牌（包括起手的 $13$ 张），依旧不能胡牌的可能的摸出牌的集合数目。

那么我们的答案就是：

$1 + \frac{\sum_{i=13}^{4n} f_{i} * (i - 13)! * (4n - i)!}{(4n - 13)!}$

先考虑如何判断一个集合能否胡牌。我们人为地规定不能取三个相同的顺子，只能取三次相同的三张。设 $g_{0/1,i,j,k}$ 为确定/没确定对子牌，考虑了前 $i$ 种牌，以 $i-1$ 为开头的顺子有 $j$ 张，以 $i$ 开头的顺子有 $k$ 张，最大可能的面子数。胡的条件就是 $\exist j, k ≤ 2,\; g_{1,n,j,k} ≥ 4$

其实 $g$ 中的 $i$ 这维是没有什么用的。我们可以将一个 $g_{0/1,j,k}$ 这样的数组压为一个状态进行下面的 $DP$ 。这也是为什么我们不用一个更显然的状态判胡牌：记录第 $i$ 、 $i-1$ 种牌分别剩几张。前者本质不同的状态数共有 $3956$ 种，而后者有近 $20000$ 种。

设 $dp_{i,j,S}$ 表示考虑前 $i$ 种牌，在其中拿了 $j$ 张牌，当前判断能否胡牌的状态是 $S$ 的摸出牌的集合数。

转移大概是： $dp_{i+1,j+x,trans(S,x)} += \dbinom{4 - org_{i+1}}{x - org_{i+1}} dp_{i,j,S}$ ，其中 $org_i$ 是初始摸到牌 $i$ 的张数。

总复杂度是 $O(Tn^2), T = 3956$

#pragma GCC optimize("2,Ofast,inline")
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 4007;
const int mod = 998244353;

template <typename T> void read(T &x) {
	int f = 0;
	register char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + (c ^ '0');
	if (f) x = -x;
}

inline void upd(int &x, register int y) {
	static int z;
	x = ((z = x + y) >= mod) ? z - mod : z;
}

int mahjong_tot;

struct status {
	int f[3][3];

	status () {
		memset(f, 0xff, sizeof f);
	}

	bool operator < (const status &b) const {
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				if (f[i][j] != b.f[i][j]) {
					return f[i][j] < b.f[i][j];
				}
			}
		}
		return 0;
	}

	bool operator == (const status &b) const {
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				if (f[i][j] != b.f[i][j]) {
					return 0;
				}
			}
		}
		return 1;
	}

	inline void chmax(int &x, register int y) {
		x = (x > y) ? x : y;
	}

	void chmax(status b) {
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				chmax(f[i][j], b.f[i][j]);
			}
		}
	}

	status trans(int b) {
		status ans;
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				if (f[i][j] == -1) continue;
				for (int k = 0; k < 3 && i + j + k <= b; ++k) {
					chmax(ans.f[j][k], f[i][j] + i + (b - i - j - k) / 3);
				}
			}
		}
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				ans.f[i][j] = min(ans.f[i][j], 4);
			}
		}
		return ans;
	}
};

struct mahjong {
	pair<status, status> sta;
	int cnt;

	mahjong() {
		cnt = 0;
		sta.first.f[0][0] = 0;
	}

	bool operator < (const mahjong &b) const {
		if (sta != b.sta) return sta < b.sta;
		if (cnt != b.cnt) return cnt < b.cnt;
		return 0;
	}

	mahjong trans(int b) {
		mahjong ans = *this;
		if (b >= 2) ++ans.cnt;
		if (ans.cnt > 7) ans.cnt = 7;
		ans.sta.first = ans.sta.first.trans(b);
		ans.sta.second = ans.sta.second.trans(b);
		if (b >= 2) {
			status tmp = (*this).sta.first.trans(b - 2);
			ans.sta.second.chmax(tmp);
		}
		return ans;
	}

	int check() {
		if (cnt == 7) return 1;
		for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				if (sta.second.f[i][j] == 4) return 1;
			}
		}
		return 0;
	}
} mah[N];
map<mahjong, int> idx;

int n, org[N], win[N];
int nex[N][5], f[2][401][N];
int fac[N], fav[N], inv[N];

void dfs_mahjong(mahjong now) {
	if (idx.find(now) != idx.end()) return;
	mah[++mahjong_tot] = now;
	win[mahjong_tot] = now.check();
	idx[now] = mahjong_tot;
	int tmp = mahjong_tot;
	for (int i = 0; i < 5; ++i) {
		dfs_mahjong(now.trans(i));
	}
}

void prework() {
	dfs_mahjong(mahjong());
	read(n);
	for (int i = 1; i <= 13; ++i) {
		int x, y;
		read(x); read(y);
		++org[x];
	}
	for (int i = 1; i <= mahjong_tot; ++i) {
		for (int j = 0; j < 5; ++j) {
			nex[i][j] = idx[mah[i].trans(j)];
		}
	}
	fac[0] = fav[0] = 1;
	inv[1] = fac[1] = fav[1] = 1;
	for (int i = 2; i < N; ++i) {
		inv[i] = 1LL * -mod / i * inv[mod % i] % mod + mod;
		fac[i] = 1LL * fac[i - 1] * i % mod;
		fav[i] = 1LL * fav[i - 1] * inv[i] % mod;
	}
}

int C(int x, int y) {
	if (x < y || y < 0) return 0;
	return 1LL * fac[x] * fav[y] % mod * fav[x - y] % mod;
}

void solve() {
	f[0][0][1] = 1;
	int now = 1;
	for (int i = 0; i < n; ++i) {
		memset(f[now], 0, sizeof f[now]);
		for (int j = 0; j <= i * 4; ++j) {
			for (int k = 1; k <= mahjong_tot; ++k) {
				if (!f[now ^ 1][j][k]) continue;
				for (int l = org[i + 1]; l < 5; ++l) {
					int to = nex[k][l];
					int del = C(4 - org[i + 1], l - org[i + 1]);
					upd(f[now][j + l][to], 1LL * f[now ^ 1][j][k] * del % mod);
				}
			}
		}
		now ^= 1;
	}
	int ans = 0;
	for (int i = 13; i <= n * 4; ++i) {
		for (int j = 1; j <= mahjong_tot; ++j) {
			if (win[j] || !f[now ^ 1][i][j]) continue;
			int del = 1LL * fac[n * 4 - i] * fac[i - 13] % mod;
			upd(ans, 1LL * del * f[now ^ 1][i][j] % mod);
		}
	}
	ans = 1LL * ans * fav[4 * n - 13] % mod;
	cout << ans << endl;
}

int main() {
	prework();
	solve();
	return 0;
}

线段树

算是一道比较签到的题。考场上想到了 $O(nm)$ 的算法但是没有调出来。

主要是转移没有考虑清楚，情况过于冗杂了。

考场debuff主要体现在这道题。

事实上 $O(nm)$ 加个线段树优化就是 $O(mlogn)$ 的了。

原问题等价于：所有修改都可以选择做或者不做，求所有情况下标记数目之和。

设 $f_{i,j}$ 表示前 $i$ 次修改后，点 $j$ 上有标记的方案数； $g_{i,j}$ 表示前 $i$ 次修改后，点 $j$ 到根的路径上有标记的方案数。

再引入一个数组 $type_{i,x}$ ， $type_{i,x}=0$ 表示第 $i$ 次修改不经过 $x$ 点； $type_{i,x} = 1$ 表示第 $i$ 次修改经过 $x$ 点，且 $x$ 不是标记点（即 $pushdown$ 过的点）； $type_{i,x}=2$ 表示第 $i$ 次修改中， $x$ 点是标记点。

对于 $f$ 的转移：

$type_x = 0, type_{fa} = 0 / 2$ ， $f_{i,x} = 2 f_{i-1,x}$
$type_x = 0, type_{fa} = 1$ ， $f_{i,x} = f_{i-1,x} + g_{i-1,x}$
$type_x = 2$ ， $f_{i,x} = f_{i-1,x} + 2^{i-1}$
$type_x = 1$ ， $f_{i,x} =f_{i-1,x}$

对于 $g$ 的转移：

$x$ 到根路径上有 $type = 2$ 的点， $g_{i,x} = g_{i-1,x} + 2^{i-1}$
$x$ 到根路径上没有 $type=2$ 的点，且 $type_{i,x} = 0$ ， $g_{i,x} = 2g_{i - 1, x}$
其他情况， $g_{i,x} = g_{i-1,x}$

分析这些转移，发现对于 $f$ 只需要实现子树乘和单点加，对于 $g$ 只需要实现子树乘、子树加和单点加，在线段树上维护即可。

$40$ 分代码：

#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int, int>
using namespace std;
const int N = 1005;
const int mod = 998244353;

template <typename T> void read(T &x) {
	int f = 0;
	register char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + (c ^ '0');
	if (f) x = -x;
}

int n, m;
int pw[N], f[N][N * 4], g[N][N * 4];
int type[N * 4];

void upd(int &x, register int y) {
	static int z;
	x = ((z = x + y) >= mod) ? (z - mod) : z;
}

void dfs1(int x, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr) {
		type[x] = 2;
		return;
 	}
	type[x] = 1;
	int mid = (l + r) >> 1;
	if (mid >= ql) dfs1(x << 1, l, mid, ql, qr);
	if (mid < qr) dfs1(x << 1 | 1, mid + 1, r, ql, qr);
}

void dfs2(int x, int fa, int l, int r, int m, int pre) {
	f[m][x] = f[m - 1][x];
	g[m][x] = g[m - 1][x];
	if (fa && type[x] == 0 && type[fa] == 1) {
		upd(f[m][x], g[m - 1][x]);
	}
	if (fa && type[x] == 0 && (type[fa] == 0 || type[fa] == 2)) {
		upd(f[m][x], f[m - 1][x]);
	}
	if (type[x] == 2) {
		upd(f[m][x], pw[m - 1]);
	}
	pre |= (type[x] == 2);
	if (pre) {
		upd(g[m][x], pw[m - 1]);
	}
	else if (type[x] == 0) {
		upd(g[m][x], g[m - 1][x]);
	}
	if (l == r) return;
	int mid = (l + r) >> 1;
	dfs2(x << 1, x, l, mid, m, pre);
	dfs2(x << 1 | 1, x, mid + 1, r, m, pre);
}

int main(){
	read(n); read(m);
	pw[0] = 1;
	for (int i = 1; i < N; ++i) {
		pw[i] = pw[i - 1] * 2 % mod;
	}
	int tot = 0;
	for (int i = 1; i <= m; ++i) {
		int opt, l, r;
		read(opt);
		if (opt == 2) {
			int ans = 0;
			for (int j = 1; j <= n * 4; ++j) {
				upd(ans, f[tot][j]);
			}
			printf("%d\n", ans);
		}
		else {
			read(l); read(r);
			memset(type, 0, sizeof type);
			dfs1(1, 1, n, l, r);
			dfs2(1, 0, 1, n, ++tot, 0);
		}
	}
	return 0;
}

$100$ 分代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int mod = 998244353;

template <typename T> void read(T &x) {
	int f = 0;
	register char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + (c ^ '0');
	if (f) x = -x;
}

void upd(int &x, register int y) {
	static int z;
	x = ((z = x + y) >= mod) ? (z - mod) : z;
}

int n, m;
int pw[N], sum[N << 2], f[N << 2], g[N << 2];
int fmul[N << 2], gmul[N << 2], gadd[N << 2];

void add_fmul(int x, int v) {
	sum[x] = 1LL * sum[x] * v % mod;
	f[x] = 1LL * f[x] * v % mod;
	fmul[x] = 1LL * fmul[x] * v % mod;
}

void mulg(int x, int v) {
	g[x] = 1LL * g[x] * v % mod;
	gmul[x] = 1LL * gmul[x] * v % mod;
	gadd[x] = 1LL * gadd[x] * v % mod;
}

void add_g(int x, int v) {
	upd(g[x], v);
	upd(gadd[x], v);
}

void pushdown(int x) {
	if (fmul[x] != 1) {
		add_fmul(x << 1, fmul[x]);
		add_fmul(x << 1 | 1, fmul[x]);
		fmul[x] = 1;
	}
	if (gmul[x] != 1) {
		mulg(x << 1, gmul[x]);
		mulg(x << 1 | 1, gmul[x]);
		gmul[x] = 1;
	}
	if (gadd[x] != 0) {
		add_g(x << 1, gadd[x]);
		add_g(x << 1 | 1, gadd[x]);
		gadd[x] = 0;
	}
}

void pushup(int x) {
	pushdown(x);
	sum[x] = f[x];
	upd(sum[x], sum[x << 1]);
	upd(sum[x], sum[x << 1 | 1]);
}

void build(int x, int l, int  r) {
	fmul[x] = gmul[x] = 1;
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(x << 1, l, mid);
	build(x << 1 | 1, mid + 1, r);
}

void update(int x, int l, int r, int ql, int qr, int m) {
	if (ql <= l && r <= qr) {
		add_g(x, pw[m - 1]);
		upd(f[x], pw[m - 1]);
		add_fmul(x << 1, 2);
		add_fmul(x << 1 | 1, 2);
		pushup(x);
		return;
	}
	pushdown(x);
	int mid = (l + r) >> 1;
	
	if (mid >= ql) {
		update(x << 1, l, mid, ql, qr, m);
	}
	else {
		int tmp = f[x << 1];
		add_fmul(x << 1, 2);
		upd(f[x << 1], mod - tmp);
		upd(f[x << 1], g[x << 1]);
		mulg(x << 1, 2);
		pushup(x << 1);
	}

	if (mid < qr) {
		update(x << 1 | 1, mid + 1, r, ql, qr, m);
	}
	else {
		int tmp = f[x << 1 | 1];
		add_fmul(x << 1 | 1, 2);
		upd(f[x << 1 | 1], mod - tmp);
		upd(f[x << 1 | 1], g[x << 1 | 1]);
		mulg(x << 1 | 1, 2);
		pushup(x << 1 | 1);
	}
	
	pushup(x);
}

int main() {
	read(n); read(m);
	pw[0] = 1;
	for (int i = 1; i < N; ++i) {
		pw[i] = pw[i - 1] * 2 % mod;
	}
	build(1, 1, n);
	int tot = 0;
	for (int i = 1; i <= m; ++i) {
		int opt, l, r;
		read(opt);
		if (opt == 1) {
			read(l); read(r);
			update(1, 1, n, l, r, ++tot);
		}
		if (opt == 2) {
			printf("%d\n", sum[1]);
		}
	}
	return 0;
}

Minimax搜索

还只会 $70$ ，先咕着。

#pragma GCC optimize("2,Ofast,inline")
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e5 + 10;
const int mod = 998244353;

template <typename T> void read(T &x) {
	int f = 0;
	register char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + (c ^ '0');
	if (f) x = -x;
}

inline void upd(int &x, register int y) {
	static int z;
	x = ((z = x + y) >= mod) ? z - mod : z;
}

int n, E, L, R;
int fir[N], nex[N << 1], arr[N << 1];
int pw[N], siz[N], ans[N], val[N], dep[N], leaf[N];

inline void Add_Edge(int x, int y) {
	nex[++E] = fir[x];
	fir[x] = E; arr[E] = y;
}

void prework(int x, int fa) {
	dep[x] = dep[fa] + 1;
	if (dep[x] & 1) val[x] = 1;
	else val[x] = n;
	leaf[x] = 1;
	for (int i = fir[x]; i; i = nex[i]) {
		if (arr[i] == fa) continue;
		leaf[x] = 0;
		prework(arr[i], x);
		siz[x] += siz[arr[i]];
		if (dep[x] & 1) val[x] = max(val[x], val[arr[i]]);
		else val[x] = min(val[x], val[arr[i]]);
	}
	if (leaf[x]) {
		siz[x]= 1;
		val[x] = x;
	}
}	

int getmin(int x, int k, int v, int fa) {
	if (leaf[x]) {
		int ans = (val[x] <= v);
		if (val[x] + k <= v) ++ans;
		return ans;
	}
	int ans = 1;
	for (int i = fir[x]; i; i = nex[i]) {
		if (arr[i] == fa) continue;
		if (dep[x] & 1) {
			ans = 1LL * ans * getmin(arr[i], k, v, x) % mod;
		}
		else if (~dep[x] & 1) {
			ans = 1LL * ans * (pw[siz[arr[i]]] - getmin(arr[i], k,  v, x)) % mod;
		}
	}
	if (~dep[x] & 1) {
		ans = ((pw[siz[x]] - ans) % mod + mod) % mod;
	}
	return ans;
}

int getmax(int x, int k, int v, int fa) {
	if (leaf[x]) {
		int ans = (val[x] >= v);
		if (val[x] - k >= v) ++ans;
		return ans;
	}
	int ans = 1;
	for (int i = fir[x]; i; i = nex[i]) {
		if (arr[i] == fa) continue;
		if (dep[x] & 1) {
			ans = 1LL * ans * (pw[siz[arr[i]]] - getmax(arr[i], k, v, x)) % mod;
		}
		else if (~dep[x] & 1) {
			ans = 1LL * ans * getmax(arr[i], k, v, x) % mod;
		}
	}
	if (dep[x] & 1) {
		ans = ((pw[siz[x]] - ans) % mod + mod) % mod;
	}
	return ans;
}

int dfs(int x, int k, int fa) {
	if (leaf[x]) return 1;
	int ans = 1;
	for (int i = fir[x]; i; i = nex[i]) {
		if (arr[i] == fa) continue;
		if (val[x] == val[arr[i]]) {
			ans = 1LL * ans * dfs(arr[i], k, x) % mod;
		}
		else if (dep[x] & 1) {
			ans = 1LL * ans * getmin(arr[i], k, val[x], x) % mod;
		}
		else if (~dep[x] & 1) {
			ans = 1LL * ans * getmax(arr[i], k, val[x], x) % mod;
		}
	}
	return ans;
}

int getans(int k) {
	if (k == 0) return 0;
	if (k == n) return pw[siz[1]] - 1;
	return ((pw[siz[1]] - dfs(1, k, 0)) % mod + mod) % mod;
}

int main() {
	read(n); read(L); read(R);
	for (int i = 1; i < n; ++i) {
		int x, y;
		read(x); read(y);
		Add_Edge(x, y);
		Add_Edge(y, x);
	}
	prework(1, 0);
	pw[0] = 1;
	for (int i = 1; i < N; ++i) {
		pw[i] = pw[i - 1] * 2 % mod;
	}
	for (int i = L - 1; i <= R; ++i) {
		ans[i] = getans(i);
	}
	for (int i = R; i >= L; --i) {
		upd(ans[i], mod - ans[i - 1]);
	}
	for (int i = L; i <= R; ++i) {
		printf("%d ", ans[i]);
	}
	puts("");
	return 0;
}