目录

• 「赛后总结」20230727 CSP 模拟赛
  • 总结
  • 题解
    • T1 卷
    • T2 简单题
    • T3 粉丝
    • T4 字符串

const ll N = 2e5 + 10, P = 1e9 + 7;
namespace SOLVE {
	ll n, w[N], f[N][2], ans;
	ldb lg[N], g[N][2];
	std::vector <ll> tu[N];
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
	inline void DFS (ll u, ll fa) {
		f[u][0] = 1, f[u][1] = w[u];
		g[u][0] = log (1), g[u][1] = log (w[u]);
		far (v, tu[u]) {
			if (v == fa) continue;
			DFS (v, u);
			if (g[v][1] > g[v][0]) g[u][0] = g[u][0] + g[v][1], f[u][0] = f[u][0] * f[v][1] % P;
			else g[u][0] = g[u][0] + g[v][0], f[u][0] = f[u][0] * f[v][0] % P;
			g[u][1] = g[u][1] + g[v][0], f[u][1] = f[u][1] * f[v][0] % P;
		}
		return;
	}
	inline void In () {
		n = rnt ();
		_for (i, 1, n) w[i] = rnt ();
		_for (i, 1, n - 1) {
			ll u = rnt (), v = rnt ();
			tu[u].push_back (v);
			tu[v].push_back (u);
		}
		return;
	}
	inline void Solve () {
		DFS (1, 0);
		return;
	}
	inline void Out () {
		printf ("%lld\n", g[1][0] > g[1][1] ? f[1][0] : f[1][1]);
		return;
	}
}

const ll N = 1e5 + 10, P = 1e7 + 19;
namespace SOLVE {
	ll n, q, num, cnt[2][2], fac[P], inv[P];
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
	inline ll FastPow (ll a, ll b) {
		ll ans = 1;
		while (b) {
			if (b & 1) ans = ans * a % P;
			a = a * a % P, b >>= 1;
		}
		return ans;
	}
	inline ll C (ll n, ll m) {
		if (n < m) return 0;
		return fac[n] * inv[n - m] % P * inv[m] % P;
	}
	inline ll Lucas (ll n, ll m) {
		if (!n) return 1;
		return Lucas (n / P, m / P) * C (n % P, m % P) % P;
	}
	inline void In () {
		n = rnt (), q = rnt ();
		return;
	}
	inline void Solve () {
		ll tmp = n, la = n, p = 0;
		while (tmp) {
			++p, tmp >>= 1;
			cnt[0][p & 1] +=  (la - tmp) / 2 + ((la & 1) && !(tmp & 1));
			cnt[1][p & 1] += ((la - tmp) / 2 + ((la & 1) && !(tmp & 1))) * p;
			la = tmp;
		}
		num = FastPow (2, cnt[0][0]);
		fac[0] = 1;
		_for (i, 1, P - 1) fac[i] = fac[i - 1] * i % P;
		inv[P - 1] = FastPow (fac[P - 1], P - 2);
		for_ (i, P - 2, 0) inv[i] = inv[i + 1] * (i + 1) % P;
		return;
	}
	inline void Out () {
		_for (i, 1, q) {
			ll m = rnt ();
			m = m - cnt[1][0] / 2 - (cnt[1][1] + cnt[0][1]) / 2 + cnt[0][1];
			if (m < 0 || m > cnt[0][1]) puts ("0");
			else printf ("%lld\n", num * Lucas (cnt[0][1], m) % P);
		}
		return;
	}
}

const ll N = 1e5 + 10;
namespace SOLVE {
	ll x, y, n, P, sq, f[N], g[N], _g[N], ans;
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
	inline ll Calc (ll limit) {
		memset (f, 0, sizeof (f));
		memset (g, 0, sizeof (g));
		memset (_g, 0, sizeof (_g));
		ll b = std::max (sq, limit);
		f[0] = g[0] = _g[0] = 1;
		_for (i, limit, b - 1) _for (j, i, n) f[j] = (f[j] + f[j - i]) % P;
		_for (i, 1, n / sq) {
			ll p = b * i;
			_for (j, i, n - p) g[j] = (g[j] + g[j - i]) % P;
			_for (j, 0, n - p) _g[j + p] = (_g[j + p] + g[j]) % P;
		}
		ll sum = 0;
		_for (i, 0, n) sum = (sum + f[i] * _g[n - i] % P) % P;
		return sum;
	}
	inline void In () {
		x = rnt (), y = rnt (), n = rnt (), P = rnt ();
		return;
	}
	inline void Solve () {
		sq = std::sqrt (n);
		ans = (Calc (x) - ((y == n) ? 0 : Calc (y + 1)) + P) % P;
		return;
	}
	inline void Out () {
		printf ("%lld\n", ans);
		return;
	}
}

const ll N = 5e6 + 10;
namespace SOLVE {
	ll n, m, d[N * 2], nxt[N * 2], mx[N * 2], ans;
	char s[N], t[N * 2];
	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}
	inline void Manacher () {
		t[1] = '#', m = 2 * n + 1;
		ll l = 0, r = -1;
		_for (i, 1, n) t[i * 2] = s[i], t[i * 2 + 1] = '#';
		_for (i, 1, m) {
			ll k = (i > r) ? 1 : std::min (d[r + l - i], r - i + 1);
			while (i - k && i + k <= m && t[i - k] == t[i + k]) ++k;
			d[i] = k;
			if (i + k > r) r = i + k, l = i - k;
		}
		return;
	}
	inline void KMP () {
		t[n + 1] = '#';
		_for (i, 1, n) t[n - i + 1] = t[n + i + 1] = s[n - i + 1];
		memset (nxt, 0, sizeof (nxt)), memset (mx, 0, sizeof (mx));
		ll j = 0;
		for_ (i, m - 1, 1) {
			while (j && t[i] != t[m - j]) j = nxt[j];
			j += (t[i] == t[m - j]), nxt[i] = j;
		}
		for_ (i, n, 1) mx[i] = std::max (mx[i + 1], nxt[i]);
		return;
	}
	inline void GetAns () {
		Manacher (), KMP ();
		_for (i, 1, m) {
			ll l = (i - d[i]) / 2, r = (i + d[i]) / 2;
			if (nxt[r] <= l) ans = std::max (ans, d[i] + 2 * nxt[r] - 1);
			if (mx[r]  >= l) ans = std::max (ans, d[i] + 2 * l - 1);
		}
		return;
	}
	inline void In () {
		scanf ("%s", s + 1);
		n = strlen (s + 1);
		return;
	}
	inline void Solve () {
		ll k = 0;
		while (k <= (n + 1) / 2 && s[k] == s[n - k + 1]) ++k;
		--k, n -= 2 * k;
		_for (i, 1, n) s[i] = s[i + k];
		s[n + 1] = '\0';
		GetAns ();
		std::reverse (s + 1, s + n + 1);
		GetAns ();
		ans += 2 * k;
		return;
	}
	inline void Out () {
		printf ("%lld\n", ans);
		return;
	}
}