#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

string p, h;

bool read(){
	if (!(cin >> p >> h))
		return false;
	return true;
}

void solve(){
	int n = h.size();
	vector<int> cntp(26);
	forn(i, p.size())
		++cntp[p[i] - 'a'];
	forn(i, n){
		vector<int> cnth(26);
		for (int j = i; j < n; ++j){
			++cnth[h[j] - 'a'];
			if (cntp == cnth){
				puts("YES");
				return;
			}
		}
	}
	puts("NO");
}

int main() {
	int tc;
	scanf("%d", &tc);
	forn(_, tc){
		read();
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int AL = 26;
string p, h;

bool read(){
	if (!(cin >> p >> h))
		return false;
	return true;
}

void solve(){
	vector<int> cntp(AL), cnt(AL);
	vector<bool> eq(AL);
	int sum = 0;
	
	auto chg = [&cntp, &cnt, &eq, &sum](int c, int val){
		sum -= eq[c];
		cnt[c] += val;
		eq[c] = (cntp[c] == cnt[c]);
		sum += eq[c];
	};
	
	forn(i, p.size())
		++cntp[p[i] - 'a'];
	forn(i, AL){
		eq[i] = (cnt[i] == cntp[i]);
		sum += eq[i];
	}
	
	int m = p.size();
	int n = h.size();
	forn(i, n){
		chg(h[i] - 'a', 1);
		if (i >= m) chg(h[i - m] - 'a', -1);
		if (sum == AL){
			puts("YES");
			return;
		}
	}
	
	puts("NO");
}

int main() {
	int tc;
	scanf("%d", &tc);
	forn(_, tc){
		read();
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

int t, a, b;

bool ok(int res, int d){
	long long sum = res * 1LL * (res + 1) / 2;
	if(sum < d) return false;
	return sum % 2 == d % 2;
}	

int main() {		
	cin >> t;
	for(int tc = 0; tc < t; ++tc){
		cin >> a >> b;
		int d = abs(a - b);
		if(d == 0){ 
			cout << "0\n";
			continue;
		}

		int res = 1;
		while(!ok(res, d)) ++res;
		cout << res << endl;
		
	}
	return 0;
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

int n;
vector<int> a;

bool read(){
	if (scanf("%d", &n) != 1)
		return false;
	a.resize(2 * n);
	forn(i, 2 * n)
		scanf("%d", &a[i]);
	return true;
}

void solve(){
	int cur = 0;
	map<int, int> difr;
	
	difr[0] = 0;
	cur = 0;
	for (int i = n; i < 2 * n; ++i){
		if (a[i] == 1)
			++cur;
		else
			--cur;
		if (!difr.count(cur))
			difr[cur] = i - (n - 1);
	}
	
	int ans = 2 * n;
	int dif = count(a.begin(), a.end(), 1) - count(a.begin(), a.end(), 2);
	
	cur = 0;
	for (int i = n - 1; i >= 0; --i){
		if (a[i] == 1)
			++cur;
		else
			--cur;
		if (difr.count(dif - cur))
			ans = min(ans, n - i + difr[dif - cur]);
	}
	if (difr.count(dif)){
		ans = min(ans, difr[dif]);
	}
	
	printf("%d\n", ans);
}

int main() {
	int tc;
	scanf("%d", &tc);
	forn(_, tc){
		read();
		solve();
	}
	return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); i++)

typedef long long li;
typedef pair<li, li> pt;

const int N = 500010;

int n;
pt a[N];
vector<int> g[N];
bool used[N];

void dfs(int v, int p = -1) {
	used[v] = true;
	for (auto to : g[v]) if (to != p) {
		if (!used[to])
			dfs(to, v);
	}
}

int main() {
	scanf("%d", &n);
	forn(i, n) scanf("%d%d", &a[i].x, &a[i].y);
	
	vector<pt> evs;
	forn(i, n) {
		evs.pb(mp(a[i].x, i));
		evs.pb(mp(a[i].y, i));
	}
	
	sort(all(evs));
	
	int cnt = 0;
	set<pt> cur;
	for (auto it : evs) {
		if (cnt >= n) break;
		if (cur.count(it)) {
			cur.erase(it);
		} else {
			int i = it.y;
			int r = a[i].y;
			for (auto jt : cur) {
				if (jt.x > r) break;
				int j = jt.y;
				g[i].pb(j);
				g[j].pb(i);
				cnt++;
				if (cnt >= n) break;
			}
			cur.insert(mp(a[i].y, i));
		}
	}
	
	dfs(0);
	puts(cnt == n - 1 && count(used, used + n, 1) == n ? "YES" : "NO");
}

#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); i++)

typedef pair<int, int> pt;

const int N = 500 * 1000 + 13;

int n;
vector<int> g[N], vs[N];
pt segs[N];

void dfs(int v, int p = -1) {
	int sum = 0;
	int bst = -1;
	for (auto to : g[v]) if (to != p) {
		dfs(to, v);
		sum += 2 * sz(vs[to]);
		if (bst == -1 || sz(vs[to]) > sz(vs[bst]))
			bst = to;
	}
	
	if (bst == -1) {
		vs[v].pb(v);
		segs[v] = mp(1, 2);
		return;
	}
	
	swap(vs[v], vs[bst]);
	int lst = segs[bst].y;
	
	sum -= 2 * sz(vs[v]);
	sum += 1;
	segs[bst].y += sum;
	
	for (auto to : g[v]) if (to != p && to != bst) {
		int add = lst - 1;
		for (auto u : vs[to]) {
			segs[u].x += add;
			segs[u].y += add;
			vs[v].pb(u);
		}
		lst = segs[to].y;
		sum -= 2 * sz(vs[to]);
		segs[to].y += sum;
		vs[to].clear();
	}
	
	vs[v].pb(v);
	segs[v] = mp(lst, segs[bst].y + 1);
}	

int main() {
	scanf("%d", &n);
	forn(i, n - 1) {
		int x, y;
		scanf("%d%d", &x, &y);
		--x; --y;
		g[x].pb(y);
		g[y].pb(x);
	}
	
	dfs(0);
	
	for (int i = 0; i < n; i++)
		printf("%d %d\n", segs[i].x, segs[i].y);
	
	return 0;
}

1278F - Cards

Во-первых, я бы хотел поблагодарить Errichto за его прекрасную лекцию по математическому ожиданию: часть 1, часть 2. Эта задача была придумана после того, как я узнал идею подсчета квадрата математического ожидания через ожидаемое количество пар — и в разборе будет использована похожая идея.

Окей, теперь сам разбор. Назовем число $$$a$$$ хорошим, если $$$1 \le a \le n$$$, и $$$a$$$-е перемешивание колоды привело к тому, что на вершине колоды оказался джокер. $$$x$$$ из нашей задачи — это количество таких хороших чисел $$$a$$$. Мы можем представить $$$x^2$$$ как количество таких пар $$$(a_1, a_2)$$$, что каждый элемент пары — хорошее число; $$$x^3$$$ как количество подобных троек, и так далее — $$$x^k$$$ представим как количество кортежей из $$$k$$$ элементов $$$(a_1, a_2, \dots, a_k)$$$, в которых каждый элемент является хорошим числом.

Теперь представим математическое ожидание $$$x^k$$$ как ожидаемое количество таких кортежей, или же как сумму $$$P(t)$$$ по всем кортежам $$$t$$$, где $$$P(t)$$$ — вероятность того, что кортеж $$$t$$$ состоит только из хороших чисел. Как посчитать эту вероятность для $$$t$$$? Так как после каждого перемешивания джокер будет на вершине колоды с вероятностью $$$\frac{1}{m}$$$, $$$P(t)$$$ должно быть равно $$$\frac{1}{m^k}$$$ — но это верно только в том случае, когда все элементы в $$$t$$$ различны. Как обработать повторяющиеся элементы? Так как все вхождения одного и того же числа являются либо хорошими, либо плохими (и вероятность того, что они все хорошие, равна $$$\frac{1}{m}$$$), точной формулой для вычисления $$$P(t)$$$ будет $$$P(t) = \frac{1}{m^d}$$$, где $$$d$$$ — количество различных элементов в кортеже.

Теперь для каждого $$$d \in [1, k]$$$ надо посчитать количество кортежей из $$$k$$$ элементов, в которых ровно $$$d$$$ различных элементов. Сделаем это при помощи динамического программирования: $$$dp_{i, j}$$$ — количество кортежей размера $$$i$$$, в которых ровно $$$j$$$ различных элементов. Каждый переход в этой динамике — это добавление нового элемента; чтобы обработать переходы из $$$dp_{i, j}$$$, мы либо добавляем новый элемент в кортеж (его можно выбрать $$$n - j$$$ способами, и мы переходим в состояние $$$dp_{i + 1, j + 1}$$$), либо добавляем уже ранее встреченный элемент (его можно выбрать $$$j$$$ способами, и мы переходим в состояние $$$dp_{i + 1, j}$$$).

Сложность решения — $$$O(k^2 \log MOD)$$$ или $$$O(k^2 + \log MOD)$$$, в зависимости от реализации.

#include<bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
const int N = 5043;

int add(int x, int y)
{
	x += y;
	while(x >= MOD) x -= MOD;
	while(x < 0) x += MOD;
	return x;
}

int mul(int x, int y)
{
	return (x * 1ll * y) % MOD;
}

int binpow(int x, int y)
{
	int z = 1;
	while(y > 0)
	{
		if(y % 2 == 1)
			z = mul(z, x);
		x = mul(x, x);
		y /= 2;
	}
	return z;
}

int inv(int x)
{
	return binpow(x, MOD - 2);
}

int n, m, k;

int dp[N][N];

int main()
{
	cin >> n >> m >> k;
	dp[0][0] = 1;
	for(int i = 0; i < k; i++)
		for(int j = 0; j < k; j++)
		{
			dp[i + 1][j] = add(dp[i + 1][j], mul(dp[i][j], j));
			dp[i + 1][j + 1] = add(dp[i + 1][j + 1], mul(dp[i][j], n - j));
		}
	int ans = 0;
	for(int i = 1; i <= k; i++)
		ans = add(ans, mul(dp[k][i], binpow(inv(m), i)));
	cout << ans << endl;
}