#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

First of all, I would like to thank Errichto for his awesome lecture on expected value: part 1, part 2. This problem was invented after I learned the concept of estimating the square of expected value from that lecture — and the editorial uses some ideas that were introduced there.

Okay, now for the editorial itself. We call a number $$$a$$$ as good if $$$1 \le a \le n$$$, and the $$$a$$$-th shuffle of the deck resulted in a joker on top. $$$x$$$ from our problem is the number of such good numbers $$$a$$$. We can represent $$$x^2$$$ as the number of pairs $$$(a_1, a_2)$$$ such that every element of the pair is a good number, $$$x^3$$$ as the number of triples, and so on — $$$x^k$$$ is the number of $$$k$$$-tuples $$$(a_1, a_2, \dots, a_k)$$$ such that each element of a tuple is a good number.

So we can rewrite the expected value of $$$x^k$$$ as the expected number of such tuples, or the sum of $$$P(t)$$$ over all tuples $$$t$$$, where $$$P(t)$$$ is the probability that $$$t$$$ consists of good numbers. How to calculate the probability that $$$t$$$ is a good tuple? Since all shuffles of the deck result in a joker with probability $$$\frac{1}{m}$$$, $$$P(t)$$$ should be equal to $$$\frac{1}{m^k}$$$ — but that is true only if all elements in $$$t$$$ are unique. How to deal with tuples with repeating elements? Since all occurences of the same element are either good or bad (with probability $$$\frac{1}{m}$$$ of being good), the correct formula for $$$P(t)$$$ is $$$P(t) = \frac{1}{m^d}$$$, where $$$d$$$ is the number of distinct elements in the tuple.

Okay, then for each $$$d \in [1, k]$$$ we have to calculate the number of $$$k$$$-tuples with exactly $$$d$$$ distinct elements. To do that, we use dynamic programming: let $$$dp_{i, j}$$$ be the number of $$$i$$$-tuples with exactly $$$j$$$ distinct elements. Each transition in this dynamic programming solution models adding an element to the tuple; if we want to compute the transitions leading from $$$dp_{i, j}$$$, we either add a new element to the tuple (there are $$$n - j$$$ ways to choose it, and we enter the state $$$dp_{i + 1, j + 1}$$$), or we add an already existing element (there are $$$j$$$ ways to choose it, and we enter the state $$$dp_{i + 1, j}$$$).

Overall complexity is $$$O(k^2 \log MOD)$$$ or $$$O(k^2 + \log MOD)$$$, depending on your implementation.

#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;
}