AtCoder Grand Contest 047 题解

AtCoder Grand Contest 047

Integer Product

考虑 $\times 10^9$ 之后质因子中 $2,5$ 的次数，卡精度。

const int M = 57, inf = 1e9;
int n, c[M][M];
ll ans;

int main() {
	ios::sync_with_stdio(0);
	rd(n);
	for (int i = 1; i <= n; i++) {
		string s;
		rds(s);
		int p = -1;
		for (ui j = 0; j < s.size(); j++)
			if (s[j] == '.') p = j;
		if (!~p) p = s.size(), s += ".0";
		while ((int)s.size() - p < 10) s += "0";
		ll a = 0;
		for (ui j = 0; j < s.size(); j++)
			if (s[j] != '.') a = a * 10 + s[j] - '0';
		int c2 = 0, c5 = 0;
		while (a % 2 == 0) ++c2, a /= 2;
		while (a % 5 == 0) ++c5, a /= 5;
		c[c2][c5]++;
	}
	for (int i = 0; i < M; i++)
		for (int j = 0; j < M; j++) {
			if (i >= 9 && j >= 9) ans += 1ll * c[i][j] * (c[i][j] - 1);
			for (int x = 0; x < M; x++)
				for (int y = 0; y < M; y++)
					if (i + x >= 18 && j + y >= 18 && (i != x || j != y))
						ans += 1ll * c[i][j] * c[x][y];
		}
	print(ans / 2);
	return 0;
}

First Second

所有字符串能生成的新字符串只有 $\mathcal O(|\Sigma|\sum_{i=1}^n |s_i|)$，Hash 判即可。

const int P[2] = {998244353, 998244853}, H = 19491001;
struct Hash {
	int a[2];
	inline Hash() {}
	inline Hash(int x) {
		a[0] = a[1] = x;
	}
	inline Hash(int x, int y) {
		a[0] = x, a[1] = y;
	}
	inline friend bool operator == (Hash x, Hash y) {
		for (int i = 0; i < 2; i++)
			if (x.a[i] != y.a[i]) return 0;
		return 1;
	}
	inline friend Hash operator + (Hash x, Hash y) {
		for (int i = 0; i < 2; i++)
			x.a[i] = (x.a[i] + y.a[i]) % P[i];
		return x;
	}
	inline friend Hash operator - (Hash x, Hash y) {
		for (int i = 0; i < 2; i++)
			x.a[i] = (x.a[i] - y.a[i] + P[i]) % P[i];
		return x;
	}
	inline friend Hash operator * (Hash x, Hash y) {
		for (int i = 0; i < 2; i++)
			x.a[i] = 1ll * x.a[i] * y.a[i] % P[i];
		return x;
	}
	inline ll h() {
		return ((ll)1e9 * a[1] + a[0]) % H;
	}
};

const Hash B = Hash(131, 13331);

const int N = 2e5 + 7;
int n, m;
string s[N];
vector<Hash> h[N];

int hh[H], he[N], hc[N], ht[N], tot;

inline void add(int x, int y, int z) {
	for (int i = hh[x]; i; i = ht[i])
		if (he[i] == y) return hc[i] += z, void();
	he[++tot] = y, hc[tot] = z, ht[tot] = hh[x], hh[x] = tot;
}

inline int ask(int x, int y) {
	for (int i = hh[x]; i; i = ht[i])
		if (he[i] == y) return hc[i];
	return 0;
}

ll ans;

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) {
		rds(s[i]), reverse(s[i].begin(), s[i].end());
		h[i].resize(s[i].size());
		h[i][0] = s[i][0];
		for (ui j = 1; j < s[i].size(); j++)
			h[i][j] = h[i][j-1] * B + s[i][j];
		add(h[i][s[i].size()-1].h(), h[i][s[i].size()-1].a[0], 1);
	}
	for (int i = 1; i <= n; i++) {
		static bool v[26];
		memset(v, 0, sizeof(v));
		for (int j = s[i].size() - 1; ~j; j--) {
			v[s[i][j]-'a'] = 1;
			if (j != (int)s[i].size() - 1) {
				Hash o = j ? h[i][j-1] : 0;
				for (int k = 0; k < 26; k++)
					if (v[k]) {
						Hash w = o * B + (k + 'a');
						ans += ask(w.h(), w.a[0]);
					}
			}
		}
	}
	print(ans);
	return 0;
}

Product Modulo

考虑找到 $P$ 的一个原根 $p$，将除了 $0$ 之外的每个数转化成 $2^k \bmod P$ 的形式，那么乘法取模就相当于指数上的循环卷积，FFT 实现，时间复杂度 $\mathcal O(P \log P)$。

取 $p=2$ 即可。

const int P = 2e5 + 3;
int n, c[P], p[P];
ll d[P], ans;

namespace FFT {
	const int N = 1 << 21 | 1;
	const ld PI = acos(-1);
	struct I {
		ld x, y;
		inline I() {}
		inline I(ld x, ld y) : x(x), y(y) {}
		inline I &operator = (int o) { return x = o, y = 0, *this; }
		inline I operator + (const I o) const { return I(x + o.x, y + o.y); }
		inline I operator - (const I o) const { return I(x - o.x, y - o.y); }
		inline I operator * (const I o) const {
			return I(x * o.x - y * o.y, x * o.y + y * o.x);
		}
	} a[N], b[N];
	int n, m, k, l, r[N];
	inline void fft(I *a, int n, int x) {
		for (int i = 0; i < n; i++) if (i < r[i]) swap(a[i], a[r[i]]);
		for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1) {
			I W = I(cos(PI / k), x * sin(PI / k));
			for (int i = 0; i < n; i += o) {
				I w = I(1, 0);
				for (int j = 0; j < k; j++, w = w * W) {
					I x = a[i+j], y = w * a[i+j+k];
					a[i+j] = x + y, a[i+j+k] = x - y;
				}
			}
		}
	}
	inline void solve() {
		k = 1, l = 0;
		while (k <= n + m) k <<= 1, ++l;
		for (int i = 0; i < k; i++)
			r[i] = (r[i>>1] >> 1) | ((i & 1) << (l - 1));
		for (int i = n + 1; i < k; i++) a[i] = 0;
		for (int i = m + 1; i < k; i++) b[i] = 0;
		fft(a, k, 1), fft(b, k, 1);
		for (int i = 0; i < k; i++) a[i] = a[i] * b[i];
		fft(a, k, -1);
		for (int i = 0; i <= n + m; i++) a[i].x /= k;
	}
}

int main() {
	rd(n);
	for (int i = 1, x; i <= n; i++) {
		rd(x);
		if (x) ++c[x];
	}
	FFT::n = FFT::m = P - 2;
	for (int i = 0; i <= P - 2; i++) {
		p[i] = i ? 2 * p[i-1] % P : 1;
		FFT::a[i] = FFT::b[i] = c[p[i]];
		d[2*i%(P-1)] -= c[p[i]];
	}
	FFT::solve();
	for (int i = 0; i <= 2 * P - 4; i++)
		d[i%(P-1)] += (ll)(FFT::a[i].x + 0.5);
	for (int i = 0; i <= P - 2; i++) ans += d[i] * p[i];
	print(ans / 2);
	return 0;
}

Twin Binary Trees

设第一棵树上的两个叶子为 $u,v$，其 LCA 为 $w$。

枚举 $w$。

枚举 $u$，设其对应的第二棵树上的叶子为 $p_u$，枚举 $p_u$ 的祖先 $x$，将 $w \to x$ 的贡献加到 $x$ 上。

枚举 $v$，设其对应的第二棵树上的叶子为 $p_v$，枚举 $p_v$ 的祖先 $y$，计算 $p_u,p_v$ 的 LCA 为 $y$ 时的贡献。

时间复杂度 $\mathcal O(n \log^2 n)$。

const int N = 1 << 18 | 1;
int n, l, r, a[N];
modint f[N], ans;

void dfs1(int p, modint w) {
	w *= p;
	if (p >= l) {
		p = a[p];
		while (p) w *= p, f[p] += w, p >>= 1;
		return;
	}
	dfs1(ls, w), dfs1(rs, w);
}

void dfs2(int p, modint w) {
	w *= p;
	if (p >= l) {
		p = a[p];
		while (p != 1) w *= p, ans += w * f[p^1] * (p >> 1), p >>= 1;
		return;
	}
	dfs2(ls, w), dfs2(rs, w);
}

void dfs3(int p) {
	if (p >= l) {
		p = a[p];
		while (p) f[p] = 0, p >>= 1;
		return;
	}
	dfs3(ls), dfs3(rs);
}

int main() {
	rd(n), l = 1 << (n - 1), r = 1 << n;
	for (int i = l; i < r; i++) rd(a[i]), a[i] += l - 1;
	for (int p = 1; p < l; p++) dfs1(ls, p), dfs2(rs, 1), dfs3(ls);
	print(ans);
	return 0;
}

Product Simulation

先把 $A,B$ 的二进制数搞出来，然后一位一位的乘再加起来即可，具体构造方式见代码。

#define p(x, a, b, c) printc(x), printc(' '), print(a, b, c)

int main() {
	print(3870);
	p('+', 0, 1, 3);
	p('<', 2, 3, 3);
	for (int x = 0; x < 2; x++) {
		p('+', 3, x, x);
		int y = x + 4;
		for (int i = 0; i < 30; i++) {
			if (i > 0) p('+', y, y, y);
			p('+', y, 3, 6);
			for (int j = i; j < 29; j++) p('+', 6, 6, 6);
			int z = i + 7 + x * 30;
			p('<', 6, x, z);
			p('+', y, z, y);
		}
	}
	for (int t = 0; t < 59; t++) {
		if (t > 0) p('+', 2, 2, 2);
		for (int i = max(t - 29, 0); i <= min(t, 29); i++) {
			int j = t - i;
			p('+', i + 7, j + 37, 4);
			p('<', 3, 4, 4);
			p('+', 2, 4, 2);
		}
	}
	return 0;
}

Rooks

咕。