多校省选模拟8

体育测试(test)

题意

给你 \(N\) 个人，你要给他们排队，每个人有一个限制，表示自己的位置必须 \(\ge a_i\)，或者是 \(\le a_i\)。

问有多少种合法的排队方法。

\(N\le 5000\)，答案对于 \(998244353\) 取模。

题解

我们考虑，如果都只有一类限制的话，答案会成啥，比如都是 \(\le a_i\) 的限制。

那么我们只要按照 \(a_i\) 从小到大排序，然后我们的答案自然就是 \(\prod_{i=1}^N(a_i-i+1)\)。

我们考虑，把一个 \(\ge a_i\) 的限制，容斥成为 \(\le n\) 的限制和 \(< a_i\) 的限制即可。

那么，我们令 \(f(i,j)\) 表示做到第 \(i\) 个，然后一共现在满足了 \(j\) 个限制的方案数。

那么，对于一个本来就是 \(\le a_i\) 的限制，她一定要被满足，转移就是

\[f(i,j)=f(i-1,j-1)\times (a_i-j+1) \]

这部分是不需要容斥的。

我们考虑对于原来的一个 \(\ge a_i\) 的限制，她分为两种转移，一个是用了 \(\le n\) 的限制，一个是用了 \(< a_i\) 的限制。分别就是

\[f(i,j)=f(i-1,j)+(-1)(a_i-j)f(i-1,j-1) \]

然后，我们考虑，最后的答案自然就是

\[\sum_{i=tot}^Nf(N,i)\times (N-i)! \]

乘上的 \((N-i)!\) 的系数表示那些选择了 \(\le N\) 的限制的那些人随便排列。

#include 
using std::cin;
using std::cout;
using std::pair;
template
inline T max(const T &x, const T &y) {
	return x > y ? x : y;
}
const int MAXN = 5e3 + 10, MOD = 1e9 + 7;
int N, fac[MAXN], F[MAXN][MAXN];
pair A[MAXN];
int main() {
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	std::ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	fac[0] = 1;
	for (int i = 1; i < MAXN; ++i) {
		fac[i] = (long long) fac[i - 1] * i % MOD;
	}
	cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> A[i].second;
		if (A[i].second > 0) {
			A[i].first = A[i].second;
		}
		else {
			A[i].first = -A[i].second - 1;
		}
	}
	std::sort(A + 1, A + 1 + N);
	F[0][0] = 1;
	int tot = 0;
	for (int i = 1; i <= N; ++i) {
		if (A[i].second > 0) {
			++tot;
			for (int j = 1; j <= i && A[i].second - j >= 0; ++j) {
				F[i][j] = F[i - 1][j - 1] * (A[i].second - j + 1LL) % MOD;
			}
		}
		else {
			for (int j = 0; j <= i; ++j) {
				F[i][j] = F[i - 1][j];
				if (j && A[i].first - j >= 0) {
					F[i][j] = (F[i][j] + (MOD - 1LL) * (A[i].first - j + 1) % MOD * F[i - 1][j - 1]) % MOD;
				}
			}
		}
	}
	int ANS = 0;
	for (int i = tot; i <= N; ++i) {
		ANS = (ANS + (long long) F[N][i] * fac[N - i]) % MOD;
	}
	cout << ANS << '\n';
	return 0;
}

一个奇怪的问题就是，在使用 std::sort 的时候，我原本的代码并没有把这个 \(A[i]\) 表示为 pair 类型，而是定义成了 int，然后写了个排序函数

sort(A + 1, A + 1 + N, [&] (const int &x, const int &y) -> {
	if (x * y > 0) {
        return abs(x) < abs(y);
    }
    else if (x < 0) {
        return -x - 1 <= y;
    }
    else {
        return x <= -y - 1;
    }
});

然后就 runtime error 了。看来以后要注意这种奇怪的 STL 问题。

贸易(trade)

题意

给你一个 \(N\) 个点的树，然后，每次你可以在树上走，每次你要卖一个货物，，由 \(A\) 的价格购入，\(B\) 的价格售出，然后你可以选择一个起点，走到终点把货物卖出去，但是卖成功的概率只有 $ ( 1-\frac{x_i}{y_i})^{len}$ 的概率，其中 \(len\) 是路径的长度，问每次给你 \(A,B,x_i,y_i\)，然后你随机一个路径，问期望收益。

题解

考场上看出来了，然后不会多点求值。我们考虑把所有情况的收益都算出来，然后除以 \(N^2\) 即可。

我们考虑长度为 \(k\) 的路径有 \(cnt_k\) 条，然后我们的答案就是 \(\frac{B\sum_{i=0}^{N-1}cnt_i p^i}{N^2}-A\)

首先 \(cnt_i\) 就是一个点分治然后就能求出来，那么我们的要点就是求 \(\sum_{i=0}^{N-1}cnt_i p^i\) 的值。

这明显就是一个以 \(cnt\) 为系数的多项式在 \(p_i\) 处的点值。

我们只要多点求值就完了。

#include 
using std::cin;
using std::cout;
using std::vector;
using std::copy;
using std::reverse;
using std::swap;
using std::cerr;
using std::function;
using std::pair;
template 
inline T min(const T &x, const T &y) {
	return x < y ? x : y;
}
template
inline T max(const T &x, const T &y) {
	return x > y ? x : y;
}
const int MAXN = 262144, MOD = 998244353;
auto Ksm = [] (int x, int y) -> int {
	int ret = 1;
	for (; y; y /= 2, x = (long long) x * x % MOD) {
		if (y & 1) {
			ret = (long long) ret * x % MOD;
		} 
	}
	return ret;
};
auto Mod = [] (int x) -> int {
	if (x >= MOD) {
		return x - MOD;
	}
	else if (x < 0) {
		return x + MOD;
	}
	else {
		return x;
	}
};
inline int ls(int k) {
	return k << 1;
}
inline int rs(int k) {
	return k << 1 | 1;
}
int SZ, R[MAXN], W[MAXN];
void INIT(int len) {
	if (SZ == len) {
		return;
	}
	SZ = len;
	for (int i = 1; i < len; ++i) {
		R[i] = (R[i >> 1] >> 1) | (i & 1 ? (len >> 1) : 0);
	}
	int wn = Ksm(3, (MOD - 1) / len);
	W[len >> 1] = 1;
	for (int i = (len >> 1) + 1; i < len; ++i) {
		W[i] = (long long) W[i - 1] * wn % MOD;
	}
	for (int i = (len >> 1) - 1; i > 0; --i) {
		W[i] = W[i << 1];
	}
	return;
}
void Ntt(vector& F, int limit, int type) {
	static unsigned long long c[MAXN];
	copy(F.begin(), F.begin() + limit, c);
	for (int i = 1; i < limit; ++i) {
		if (i < R[i]) {
			swap(c[i], c[R[i]]);
		}
	}
	for (int o = 2, j = 1; o <= limit; o <<= 1, j <<= 1) {
		for (int i = 0; i < limit; i += o) {
			for (int k = 0; k < j; ++k) {
				unsigned long long OI = c[i + j + k] * W[k + j] % MOD;
				c[i + j + k] = c[i + k] + MOD - OI;
				c[i + k] += OI;
			}
		}
	}
	if (type == -1) {
		reverse(c + 1, c + limit);
		int inv = Ksm(limit, MOD - 2);
		for (int i = 0; i < limit; ++i) {
			c[i] = c[i] * inv % MOD;
		}
	}
	for (int i = 0; i < limit; ++i) {
		F[i] = c[i] % MOD;
	}
	return;
}
struct Poly {
	vector v;
	int& operator [] (const int &pos) {
		return v[pos];
	}
	int len() {
		return v.size();
	}
	void set(int l) {
		return v.resize(l);
	}
	void clear() {
		v.clear();
		return;
	}
	void adjust() {
		while (v.size() > 1 && !v.back()) {
			v.pop_back();
		}
		return;
	}
	void rev() {
		reverse(v.begin(), v.end());
	}
	void Ntt(int L, int type) {
		int limit = 1 << L;
		INIT(limit);
		set(limit);
		::Ntt(v, limit, type);
		return;
	}
	void Squ() {
		int L = ceil(log2(len())) + 1, limit = 1 << L;
		Ntt(L, 1);
		for (int i = 0; i < limit; ++i) {
			v[i] = (long long) v[i] * v[i] % MOD;
		}
		Ntt(L, -1);
		return adjust();
	}
	void operator += (Poly &x) {
		if (len() < x.len()) {
			set(x.len());
		}
		for (int i = 0; i < x.len(); ++i) {
			v[i] = Mod(v[i] + x[i]);
		}
		adjust();
		return;
	}
	void operator -= (Poly &x) {
		if (len() < x.len()) {
			set(x.len());
		}
		for (int i = 0; i < x.len(); ++i) {
			v[i] = Mod(v[i] - x[i]);
		}
		adjust();
		return;
	}
	Poly operator * (Poly &x) {
		Poly ret, tmp0 = *this, tmp1 = x;
		int L = ceil(log2(tmp0.len() + tmp1.len() - 1)), n = 1 << L;
		Ntt(L, 1);
		x.Ntt(L, 1);
		ret.set(n);
		for (int i = 0; i < n; ++i) {
			ret[i] = (long long) x[i] * v[i] % MOD;
		}
		ret.Ntt(L, -1);
		ret.adjust();
		*this = tmp0;
		x = tmp1;
		return ret;
	}
	Poly operator - (Poly &x) {
		Poly ret;
		ret.set(max(len(), x.len()));
		for (int i = 0; i < len(); ++i) {
			ret[i] = v[i];
		}
		for (int i = 0; i < x.len(); ++i) {
			ret[i] = Mod(ret[i] - x[i]);
		}
		return ret;
	}
	Poly operator + (Poly &x) {
		Poly ret;
		ret.set(max(len(), x.len()));
		for (int i = 0; i < len(); ++i) {
			ret[i] = v[i];
		}
		for (int i = 0; i < x.len(); ++i) {
			ret[i] = Mod(ret[i] + x[i]);
		}
		return ret;
	}
	void operator *= (Poly &x) {
		Poly tmp = x;
		int L = ceil(log2(len() + x.len() - 1)), n = 1 << L;
		Ntt(L, 1);
		x.Ntt(L, 1);
		for (int i = 0; i < n; ++i) {
			v[i] = (long long) v[i] * x[i] % MOD;
		}
		Ntt(L, -1);
		adjust();
		x = tmp;
	}
	Poly GetInv(int deg = -1) {
		if (!~deg) {
			deg = len();
		}
		if (deg == 1) {
			return {{Ksm(v[0], MOD - 2)}};
		}
		Poly ret = GetInv((deg + 1) / 2), tmp;
		int L = ceil(log2(deg)) + 1, n = 1 << L, mx = min(len(), deg);
		tmp.set(deg);
		for (int i = 0; i < mx; ++i) {
			tmp[i] = v[i];
		}
		tmp.Ntt(L, 1);
		ret.Ntt(L, 1);
		for (int i = 0; i < n; ++i) {
			ret[i] = (2 - (long long) tmp[i] * ret[i] % MOD + MOD) * ret[i] % MOD;
		}
		ret.Ntt(L, -1);
		ret.set(deg);
		return ret;
	}
	pair operator % (Poly &x) {
		if (x.len() > len()) {
			return {{{0}}, *this};
		}
		Poly tmp0 = *this, tmp1 = x;
		tmp0.rev();
		tmp1.rev();
		tmp1 = tmp1.GetInv(len() - x.len() + 1);
		tmp0 *= tmp1;
		tmp0.set(len() - x.len() + 1);
		tmp0.rev();
		tmp1 = tmp0 * x;
		Poly ret = *this - tmp1;
		ret.set(x.len() - 1);
		return {tmp0, ret};
	}
	vector getmulpointvalue(vector x) {
		static Poly tmp[MAXN * 4];
		function get = [&] (int u, int l, int r) -> void {
			if (l == r) {
				tmp[u] = {{Mod(-x[l]), 1}};
				return;
			}
			int mid = (l + r) / 2;
			get(ls(u), l, mid);
			get(rs(u), mid + 1, r);
			tmp[u] = tmp[ls(u)] * tmp[rs(u)];
			return;
		};
		get(1, 0, x.size() - 1);
		vector ret(x.size());
		function solve = [&] (int l, int r, Poly f, int u) -> void {
			if (l == r) {
				ret[l] = f[0];
				return;
			}
			int mid = (l + r) / 2;
			solve(l, mid, (f % tmp[ls(u)]).second, ls(u));
			solve(mid + 1, r, (f % tmp[rs(u)]).second, rs(u));
		};
		solve(0, x.size() - 1, (*this % tmp[1]).second, 1);
		return ret;
	}
};
int N, M, S, mxd, vis[MAXN], sz[MAXN], A[MAXN], B[MAXN];
long long cnt[MAXN];
vector v[MAXN];
Poly buc;
int getrt(int nw, int fa) {
	sz[nw] = 1;
	int mx = 0;
	for (auto &j: v[nw]) {
		if (j != fa && !vis[j]) {
			int t = getrt(j, nw);
			if (t) {
				return t;
			}
			sz[nw] += sz[j];
			mx = max(mx, sz[j]);
		}
	}
	if (max(mx, S - sz[nw]) <= S / 2) {
		return nw;
	}
	return 0;
}
void get_sz(int nw, int fa, int dep) {
	sz[nw] = 1;
	if (dep >= buc.v.size()) {
		buc.v.push_back(1);
	}
	else {
		++buc[dep];
	}
	for (auto &j: v[nw]) {
		if (!vis[j] && fa != j) {
			get_sz(j, nw, dep + 1);
			sz[nw] += sz[j];
		}
	}
}
void calc(int x) {
	buc.Squ();
	if (x > 0) {
		for (int i = 0; i < buc.len(); ++i) {
			cnt[i] += buc[i];
		}
	}
	else {
		for (int i = 0; i < buc.len(); ++i) {
			cnt[i] -= buc[i];
		}
	}
	buc.clear();
}
void solve(int nw) {
	vis[nw] = 1;
	mxd = 0;
	get_sz(nw, 0, 0);
	calc(1);
	for (auto &j: v[nw]) {
		if (!vis[j]) {
			mxd = 0;
			buc.v.push_back(0);
			get_sz(j, 0, 1);
			calc(-1);
			S = sz[j];
			solve(getrt(j, 0));
		}
	}
}
int main() {
	freopen("trade.in", "r", stdin);
	freopen("trade.out", "w", stdout);
	std::ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	S = N;
	for (int i = 1, x, y; i < N; ++i) {
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	solve(getrt(1, 0));
	Poly dis;
	dis.set(N);
	for (int i = 0; i < N; ++i) {
		dis[i] = cnt[i] % MOD;
	}
	vector p;
	for (int i = 1, x, y; i <= M; ++i) {
		cin >> A[i] >> B[i] >> x >> y;
		p.push_back(Mod(1 - (long long) x * Ksm(y, MOD - 2) % MOD));
	}
	p = dis.getmulpointvalue(p);
	for (int i = 1, inv = Ksm((long long) N * N % MOD, MOD - 2); i <= M; ++i) {
		cout << Mod((long long) B[i] * p[i - 1] % MOD * inv % MOD - A[i]) << '\n';
	}
	return 0;
}

密码(password)

题意

通信题

给你一个 \(n\) 长度的 \(01\) 串 \(a\)，然后你要返回一个 \(m\) 长度的 \(01\) 串 \(b\)，然后强制固定 \(k\) 个位置的 \(0\) 或 \(1\)，然后你还要能给你一个 \(m\) 个长度的 \(01\) 串，你能把 \(n\) 的那个串返回出来，但是不告诉你 \(k\) 个位置都是啥。

题解

我们考虑，随机 \(m\) 个 \(n\) 长度的 \(01\) 串，然后那个 \(m\) 个串的每个 \(01\) 位就表示异或不异或第 \(i\) 个 \(n\) 长度的 \(01\) 串。

解码的时候就直接异或出来就是原来的串。

编码的时候，我们要根据这 \(m\) 个随机串，能异或出来我们原来的 \(a\) 串，首先，我们令异或的答案是 \(g\)，然后 \(g\) 首先要搞上那 \(k\) 个位置里是 \(1\) 的 \(01\) 串，那么，我们要把剩下这 \(g\) 改成 \(a\)，我们只要把剩下的 \(m-k\) 个 \(01\) 串建立一个线性基，然后按位构造就好了。

我们考虑这样的成功概率，自然就是 \(m\) 个 \(n\) 维 \(01\) 向量满秩的概率，然后假定存在一组 \(n\) 个不相关 \(n\) 维向量的概率。

考虑正难则反，算不存在的概率，

这个玩意不好算，但是我们可以算出来他的上界。

应该是 \(\prod_{i=1}^N{(1-\frac{1}{2^i})}\times (\frac{1}{2^{50}})\)。这玩意很接近 \(0\) 了，那么成功的概率就大概是 \(1\)。

#include "password.h"
#include 
using std::bitset;
const long long s1 = 292828, s2 = 2836372, s3 = 998244353;
long long seed;
inline long long mrand() {
	return seed = (seed * s1 + s2 + rand()) % s3;
}
bitset<1000> d[1010];
bitset<2050> p[1010];
void encoder(int _n, int m, int k, const char *a, const char *b, char *ans) {
	srand(20130508);
	bitset<1000> f, g;
	bitset<2050> e;
	seed = 0;
	f.reset();
	g.reset();
	e.reset();
	mrand();
	for (int i = 0; i < _n; ++i) {
		g[i] = a[i] - '0';
	}
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < _n; ++j) {
			f[j] = mrand() & 1;
		}
		if (b[i] == '0') {
			continue;
		}
		else if (b[i] == '1') {
			g ^= f;
		}
		else {
			e[i] = 1;
			std::function, bitset<2050>)> solve = [&] (bitset<1000> a, bitset<2050> b) {
				for (int i = _n - 1; ~i; --i) {
					if (a[i]) {
						if (d[i][i]) {
							a ^= d[i];
							b ^= p[i];
						}
						else {
							d[i] = a;
							p[i] = b;
							break;
						}
					}
				}
				return;
			};
			solve(f, e);
			e[i] = 0;
		}
	}
	bitset<2050> h;
	h.reset();
	for (int i = 0; i < m; ++i) {
		h[i] = b[i] == '1';
	}
	for (int i = _n - 1; ~i; --i) {
		if (g[i]) {
			g ^= d[i];
			h ^= p[i];
		}
	}
	for (int i = 0; i < m; ++i) {
		ans[i] = '0' + h[i];
	}
}
void decoder(int _n, int m, const char *a, char *ans) {
	srand(20130508);
	seed = 0;
	mrand();
	bitset<1000> b, c;
	b.reset();
	c.reset();
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < _n; ++j) {
			b[j] = mrand() & 1;
		}
		if (a[i] == '1') {
			c ^= b;
		}
	}
	for (int i = 0; i < _n; ++i) {
		ans[i] = '0' + c[i];
	}
	return;
}