[problem:2236A]↵
↵
Idea: [user:arsen1y,2026-06-13]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2236A]↵
</spoiler>↵
↵
<spoiler summary="Solution (arsen1y)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define int long long↵
↵
using namespace std;↵
↵
const int INF = (int) 1e18;↵
↵
int32_t main() {↵
std::ios::sync_with_stdio(false);↵
cin.tie(NULL);↵
cout.tie(NULL);↵
↵
int _;↵
cin >> _;↵
↵
while (_--) {↵
int n;↵
cin >> n;↵
↵
vector <int> a(n);↵
int mx = -INF;↵
int mn = INF;↵
for (int i = 0; i < n; ++i) {↵
cin >> a[i];↵
mx = max(mx, a[i]);↵
mn = min(mn, a[i]);↵
}↵
↵
cout << mx - mn + 1 << "\n";↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2236B]↵
↵
Idea: [user:eyfxrby,2026-06-13]↵
↵
<spoiler summary="Hint">↵
Try to find a property that does not change during operations.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2236B]↵
</spoiler>↵
↵
<spoiler summary="Solution (eyfxrby)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
int t;↵
cin >> t;↵
while (t--) {↵
int n, k; cin >> n >> k;↵
string s; cin >> s;↵
vector<int> cnt(k, 0);↵
for (int i = 0; i < n; i++) cnt[i % k] += s[i] - '0';↵
bool ok = true;↵
for (int r = 0; r < k; r++) {↵
if (cnt[r] % 2) {↵
ok = false;↵
break;↵
}↵
}↵
cout << (ok ? "YES" : "NO") << '\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2236C]↵
↵
Idea: [user:arsen1y,2026-06-13]↵
↵
<spoiler summary="Hint">↵
It can be shown that it is advantageous to do only divisions first, and then only additions.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2236C]↵
</spoiler>↵
↵
<spoiler summary="Solution (arsen1y)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define int long long↵
↵
using namespace std;↵
↵
const int INF = (int) 1e18;↵
↵
int32_t main() {↵
int _;↵
cin >> _;↵
↵
while (_--) {↵
int a, b, x;↵
cin >> a >> b >> x;↵
↵
int ans = INF;↵
int i = 0;↵
while (a != b) {↵
if (b > a) {↵
swap(a, b);↵
}↵
↵
ans = min(ans, abs(a - b) + i);↵
a /= x;↵
i++;↵
}↵
↵
ans = min(ans, i);↵
↵
cout << ans << "\n";↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2236D]↵
↵
Idea: [user:dvb1r,2026-06-13]↵
↵
<spoiler summary="Hint 1">↵
What happens if Arseny chooses the maximum of the array as his first move?↵
↵
<spoiler summary="Answer">↵
If the count of maximum is odd, then Dabir wins, otherwise Egor wins.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Try to look at the second maximum.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2236D]↵
</spoiler>↵
↵
<spoiler summary="Solution (dvb1r)">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
void solve();↵
↵
int main() {↵
int t; cin >> t;↵
while (t--) solve();↵
return 0;↵
}↵
↵
void solve() {↵
int n, k; cin >> n >> k;↵
vector<int> A(n);↵
for (auto& x : A) cin >> x;↵
sort(A.begin(), A.end());↵
vector<pair<int, int>> a = {{A[0], 1}};↵
for (int i = 1; i < n; ++i) {↵
if (A[i] == A[i - 1]) a.back().second++;↵
else a.emplace_back(A[i], 1);↵
}↵
↵
while (a.size() > 0) {↵
n = a.size();↵
if (a[n - 1].second % 2 == 0) {↵
cout << "YES\n";↵
return;↵
}↵
if (n == 1) {↵
cout << "NO\n";↵
return;↵
}↵
if (a[n - 1].first - a[n - 2].first <= k) {↵
cout << "YES\n";↵
return;↵
}↵
a.pop_back();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2236E]↵
↵
Idea: [user:arsen1y,2026-06-13]↵
↵
<spoiler summary="Hint 1">↵
The cut segments of the array do not need to be checked for non-intersection.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Try to save information about all the good segments, and only then find the answer.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2236E]↵
</spoiler>↵
↵
<spoiler summary="Solution (dvb1r)">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
void solve();↵
↵
int main() {↵
int t = 1; cin >> t;↵
while (t--) solve();↵
return 0;↵
}↵
↵
void solve() {↵
int n; cin >> n;↵
vector<int> a(n);↵
for (auto& x : a) cin >> x, --x;↵
vector<vector<bool>> able(n, vector<bool>(n));↵
for (int i = 0; i < n; ++i) {↵
vector<int> us(n);↵
int mn = a[i], mx = a[i];↵
for (int j = i; j < n; ++j) {↵
if (us[a[j]]) break;↵
us[a[j]] = 1;↵
mn = min(mn, a[j]), mx = max(mx, a[j]);↵
if (mx - mn == j - i) able[mn][mx] = 1;↵
}↵
}↵
↵
for (int ans = n; ans > 0; --ans) {↵
for (int i = 0; i + 2 * ans <= n; ++i) {↵
if (able[i][i + ans - 1] && able[i + ans][i + 2 * ans - 1]) {↵
cout << ans << '\n';↵
return;↵
}↵
}↵
}↵
cout << "0\n";↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2236F1]↵
↵
Idea: [user:eyfxrby,2026-06-13]↵
↵
<spoiler summary="Hint 1">↵
What can we say about $gcd(p_i, p_j)$ for any pair $(i, j)$?↵
↵
<spoiler summary="Ответ">↵
$gcd(p_i, p_j) = 1$.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Let's take a simple number $pr$. How many elements of the array $p$ can be divisible by this $pr$?↵
↵
<spoiler summary="Ответ">↵
No more than one.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2236F1]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <bits/stdc++.h>↵
#include <immintrin.h>↵
↵
using namespace __gnu_pbds;↵
using namespace std;↵
↵
#define eps 1e-7↵
#define MOD2 119 * (1ll << 23) + 1↵
#define int long long↵
#define mp make_pair↵
#define pll pair <long long, long long>↵
#define next return↵
#define skip continue↵
#define all(a) a.begin(), a.end()↵
#define rall(a) a.rbegin(), a.rend()↵
#define f first↵
#define max_of max_element↵
#define min_of min_element↵
#define s second↵
↵
// const int MAX_MEM = 4e8;↵
// int mpos = 0;↵
// alignas(long long) char mem[MAX_MEM];↵
// inline void * operator new(size_t n) {↵
// if (n & 7) n += 8 - (n & 7);↵
// char *res = mem + mpos;↵
// mpos += n;↵
// return (void *)res;↵
// }↵
// void operator delete(void *) {}↵
↵
int scan() {↵
int x;↵
cin >> x;↵
return x;↵
}↵
↵
string read() {↵
string s;↵
cin >> s;↵
return s;↵
}↵
↵
const int N = 1e6 + 5, MOD = 1e9 + 7;↵
int lp[N], a[N], x, n, v[101];↵
vector<int> pr, divs[N];↵
↵
int bin_pow(int x, int n) {↵
int res = 1;↵
while (n) {↵
if ((n & 1)) res = res * x % MOD;↵
n >>= 1;↵
x = x * x % MOD;↵
}↵
return res;↵
}↵
↵
int solveF1_AUTHOR() {↵
map <int, int> cnt;↵
int cur_x;↵
int mx = *max_element(a + 1, a + n + 1);↵
set <int> setik;↵
for (int i = 1; i <= n; i++) {↵
int val = a[i];↵
cur_x = val;↵
while (cur_x > 1) {↵
setik.insert(lp[cur_x]);↵
cnt[lp[cur_x]]++;↵
cur_x /= lp[cur_x];↵
}↵
}↵
int ans = 1;↵
for (auto prime: setik) {↵
int sum = 1;↵
//cout << prime << ' ' << cnt[prime] << '\n';↵
ans = (ans * (cnt[prime] + 1)) % MOD;↵
}↵
return ans;↵
}↵
↵
↵
int32_t main() {↵
lp[1] = 1;↵
for (int i = 2; i < N; i++) {↵
if (lp[i] == 0) {↵
pr.push_back(i);↵
lp[i] = i;↵
}↵
for (int j = 0; j < (int) pr.size() && pr[j] <= lp[i] && i * pr[j] < N; j++) {↵
lp[i * pr[j]] = pr[j];↵
}↵
}↵
int t = scan();↵
while (t--) {↵
n = scan(); x = scan();↵
for (int i = 1; i <= n; i++) a[i] = scan();↵
cout << solveF1_AUTHOR() << '\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2236F2]↵
↵
Idea: [user:eyfxrby,2026-06-13]↵
↵
<spoiler summary="Hint 1">↵
Try to fix the prime number $pr$. How can we transform the condition of the perfect array $p$ using $v_{pr}$?↵
↵
<spoiler summary="Answer">↵
$x \cdot lcm(p_1, p_2, \ldots, p_n) = p_1 \cdot p_2 * \ldots \cdot p_n <=> max(v_{pr}(p_i)) + v_{pr}(x) = \sum(v_{pr}(p_i)$)↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider what a simple $pr$ might be. What types of $pr$ can it be classified into?↵
↵
<spoiler summary="Answer">↵
$x$ is divisible by $pr$, and $x$ is not divisible by $pr$.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Think about how to solve each of the cases in hint 2.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2236F2]↵
</spoiler>↵
↵
<spoiler summary="Solution 1 (eyfxrby)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <bits/stdc++.h>↵
#include <immintrin.h>↵
↵
using namespace __gnu_pbds;↵
using namespace std;↵
↵
#define eps 1e-7↵
#define MOD2 119 * (1ll << 23) + 1↵
#define int long long↵
#define mp make_pair↵
#define pll pair <long long, long long>↵
#define next return↵
#define skip continue↵
#define all(a) a.begin(), a.end()↵
#define rall(a) a.rbegin(), a.rend()↵
#define f first↵
#define max_of max_element↵
#define min_of min_element↵
#define s second↵
↵
int scan() {↵
int x;↵
cin >> x;↵
return x;↵
}↵
↵
string read() {↵
string s;↵
cin >> s;↵
return s;↵
}↵
↵
const int N = 1e6 + 2, MOD = 1e9 + 7;↵
int lp[N], a[N], x, n, v[N];↵
vector<int> pr, divs[N];↵
↵
int MAX_V = -1E9;↵
↵
int solve_for_prime(int vp) {↵
int mx_pref = 0;↵
int S = 0;↵
for (int i = 1; i <= n; i++) S += v[i];↵
S = min(S, 36ll);↵
int dp[MAX_V + 1][MAX_V + S + 2];↵
int old_pref_sum[MAX_V + 1][MAX_V + S + 2];↵
int old_pref_sum2[MAX_V + 1][MAX_V + S + 2];↵
memset(dp, 0, sizeof dp);↵
memset(old_pref_sum, 0, sizeof old_pref_sum);↵
memset(old_pref_sum2, 0, sizeof old_pref_sum2);↵
int sum = 0;↵
dp[0][0] = 1;↵
for (int i = 0; i <= n; i++) {↵
for (int sum_vp = 0; sum_vp <= S && i > 0; sum_vp++) {↵
for (int new_max = 1; new_max <= min(sum_vp, v[i]); new_max++) {↵
dp[new_max][sum_vp] += old_pref_sum2[new_max - 1][sum_vp - new_max];↵
if (dp[new_max][sum_vp] >= MOD) dp[new_max][sum_vp] -= MOD;↵
}↵
for (int old_max = 0; old_max <= min(mx_pref, sum_vp); old_max++) {↵
dp[old_max][sum_vp] += (old_pref_sum[old_max][sum_vp] + MOD - (sum_vp - min(old_max, v[i]) - 1 < 0 ? 0 :↵
old_pref_sum[old_max][sum_vp - min(old_max, v[i]) - 1])) % MOD;↵
//if (dp[old_max][sum_vp] >= MOD) dp[old_max][sum_vp] -= MOD;↵
↵
}↵
}↵
for (int old_max = 0; old_max <= MAX_V; old_max++) {↵
for (int j = 0; j <= MAX_V + S; j++) {↵
old_pref_sum[old_max][j] = 0;↵
old_pref_sum[old_max][j] = (!j ? dp[old_max][j] : old_pref_sum[old_max][j - 1] + dp[old_max][j]);↵
if (old_pref_sum[old_max][j] >= MOD) old_pref_sum[old_max][j] -= MOD;↵
}↵
}↵
for (int j = 0; j <= MAX_V + S; j++) {↵
for (int old_max = 0; old_max <= MAX_V; old_max++) {↵
old_pref_sum2[old_max][j] = 0;↵
old_pref_sum2[old_max][j] = (!old_max ? dp[old_max][j] : old_pref_sum2[old_max - 1][j] + dp[old_max][j]);↵
if (old_pref_sum2[old_max][j] >= MOD) old_pref_sum2[old_max][j] -= MOD;↵
if(i != n) dp[old_max][j] = 0;↵
}↵
}↵
mx_pref = max(mx_pref, v[i]);↵
}↵
int ret = 0;↵
for (int mx = 1; vp + mx <= S && mx <= MAX_V; mx++) {↵
ret = (ret + dp[mx][vp + mx]);↵
if (ret >= MOD) ret -= MOD;↵
}↵
return ret;↵
}↵
↵
int solveF2_AUTHOR() {↵
map<int, int> cnt_pr;↵
int cur_x = x;↵
while (cur_x > 1) {↵
int next_div = lp[cur_x];↵
cnt_pr[next_div]++;↵
cur_x /= next_div;↵
}↵
int ans = 1;↵
for (auto [prime, cnt]: cnt_pr) {↵
MAX_V = -1e9;↵
for (int i = 1; i <= n; i++) {↵
cur_x = a[i];↵
v[i] = 0;↵
while (cur_x % prime == 0) {↵
v[i]++;↵
cur_x /= prime;↵
}↵
MAX_V = max(MAX_V, v[i]);↵
}↵
ans = (ans * solve_for_prime(cnt)) % MOD;↵
}↵
map <int, int> cnt;↵
int mx = *max_element(a + 1, a + n + 1);↵
set <int> setik;↵
for (int i = 1; i <= n; i++) {↵
int val = a[i];↵
cur_x = val;↵
while (cur_x > 1) {↵
cnt[lp[cur_x]]++;↵
setik.insert(lp[cur_x]);↵
cur_x /= lp[cur_x];↵
}↵
}↵
for (auto prime: setik) {↵
//if (2 * prime > mx) break;↵
int sum = 1;↵
if (x % prime != 0) ans = (ans * (cnt[prime] + 1)) % MOD;↵
}↵
return ans;↵
}↵
↵
↵
int32_t main() {↵
for (int i = 2; i < N; i++) {↵
if (lp[i] == 0) {↵
pr.push_back(i);↵
lp[i] = i;↵
}↵
for (int j = 0; j < (int) pr.size() && pr[j] <= lp[i] && i * pr[j] < N; j++) {↵
lp[i * pr[j]] = pr[j];↵
}↵
}↵
int t = scan();↵
while (t--) {↵
n = scan(), x = scan();↵
for (int i = 1; i <= n; i++) a[i] = scan();↵
cout << solveF2_AUTHOR() << '\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Solution 2 (Treks)">↵
~~~~~↵
//#pragma GCC optimize("Ofast")↵
//#pragma GCC optimize("O3,unroll-loops")↵
↵
#include <bits/stdc++.h>↵
#include <experimental/random>↵
#include <ext/pb_ds/assoc_container.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
using ll = long long;↵
using ld = long double;↵
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;↵
using str = string;↵
const ll INF = 1e18, MOD = 1e9 + 7;↵
template<class T> using pq_min = priority_queue<T, vector<T>, greater<T>>;↵
template<class T> using pq_max = priority_queue<T, vector<T>, less<T>>;↵
#define int long long↵
↵
void solve();↵
↵
vector<int> P;↵
const int Mx = 1e4;↵
↵
signed main() {↵
vector<bool> us(Mx);↵
for (int i = 2; i < Mx; ++i) {↵
if (!us[i]) {↵
P.push_back(i);↵
for (int j = i * i; j < Mx; j += i) {↵
us[j] = true;↵
}↵
}↵
}↵
#ifdef LOCAL↵
freopen("input.txt", "r", stdin);↵
freopen("output.txt", "w", stdout);↵
#endif↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
ll q = 1;↵
cin >> q;↵
while (q--) {↵
solve();↵
cout << "\n";↵
}↵
}↵
↵
void solve() {↵
int n, x;↵
cin >> n >> x;↵
map<int, int> cnt;↵
for (auto w: P) {↵
if (w * w > x) {↵
break;↵
}↵
while (x % w == 0) {↵
x /= w;↵
cnt[w]++;↵
}↵
}↵
if (x > 1) {↵
cnt[x]++;↵
}↵
vector<int> a(n);↵
for (int i = 0; i < n; ++i) {↵
cin >> a[i];↵
}↵
map<int, vector<int>> w1;↵
for (int i = 0; i < n; ++i) {↵
for (auto w: P) {↵
if (w * w > a[i]) {↵
break;↵
}↵
int sum = 0;↵
while (a[i] % w == 0) {↵
a[i] /= w;↵
sum++;↵
}↵
if (sum > 0) {↵
w1[w].push_back(sum);↵
}↵
}↵
if (a[i] > 1) {↵
w1[a[i]].push_back(1);↵
}↵
}↵
int Ans = 1;↵
for (auto [id, e]: w1) {↵
int mx = 0;↵
for (auto s: e) {↵
mx = max(mx, s);↵
}↵
vector<vector<int>> dp(cnt[id] + 1, vector<int>(mx + 1));↵
dp[0][0] = 1;↵
for (auto w: e) {↵
vector<vector<int>> dp1(cnt[id] + 1, vector<int>(mx + 1));↵
for (int i = 0; i <= w; ++i) {↵
for (int j = 0; j <= cnt[id]; ++j) {↵
for (int k = 0; k <= mx; ++k) {↵
if (j + min(i, k) <= cnt[id]) {↵
dp1[j + min(i, k)][max(i, k)] += dp[j][k];↵
dp1[j + min(i, k)][max(i, k)] %= MOD;↵
}↵
}↵
}↵
}↵
swap(dp, dp1);↵
}↵
int s = 0;↵
for (int i = 0; i <= mx; ++i) {↵
s += dp[cnt[id]][i];↵
}↵
s %= MOD;↵
Ans *= s;↵
Ans %= MOD;↵
cnt[id] = 0;↵
}↵
for (auto s: cnt) {↵
if (s.second > 0) {↵
Ans = 0;↵
}↵
}↵
cout << Ans;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2236G]↵
↵
Idea: [user:dvb1r,2026-06-13]↵
↵
<spoiler summary="Hint 1">↵
In fact, the XOR of non-negative numbers is always less or equal their sum, and you can think about why.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Using the fact that the XOR of a set of numbers is equal to the sum of those numbers, how many non-zero numbers can there be in this set?↵
↵
<spoiler summary="Answer">↵
No more than $log(A)$, since each bit must occur at most once.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
For each vertex, pre-calculate the closest ancestor on the vertical path that violates the good segment condition.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Reduce the problem to a path of length at most $2 * log(A)$, and calculate the rest using the pre-calculation from hint 3.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2236G]↵
</spoiler>↵
↵
<spoiler summary="Solution 1 (dvb1r)">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
void solve();↵
↵
int main() {↵
int t = 1;↵
cin >> t;↵
while (t --> 0) solve();↵
return 0;↵
}↵
↵
struct Graph {↵
vector<int> tin, tout, d;↵
vector<vector<pair<int, ll>>> up;↵
↵
int timer;↵
↵
void dfs(int v, const vector<vector<int>>& g, const vector<int>& arr, int p = -1) {↵
tin[v] = timer++;↵
up[0][v] = {p, arr[v]};↵
for (int l = 1; l < 20; ++l) {↵
if (up[l - 1][v].first == -1) {↵
up[l][v] = {-1, 0};↵
continue;↵
}↵
up[l][v].first = up[l - 1][up[l - 1][v].first].first;↵
up[l][v].second = up[l - 1][up[l - 1][v].first].second + up[l - 1][v].second;↵
}↵
for (int u : g[v]) {↵
if (u == p) continue;↵
d[u] = d[v] + 1;↵
dfs(u, g, arr, v);↵
}↵
tout[v] = timer;↵
}↵
↵
Graph(const vector<vector<int>>& g, const vector<int>& a) : tin(g.size()), tout(g.size()), d(g.size()), up(20, vector<pair<int, ll>>(g.size())) {↵
timer = 0;↵
dfs(0, g, a);↵
}↵
↵
bool anc(int p, int v) {↵
return tin[p] <= tin[v] && tout[p] >= tout[v];↵
}↵
↵
int getLenVertical(int u, int v) {↵
if (!anc(u, v)) swap(u, v);↵
assert(anc(u, v));↵
return d[v] - d[u] - 1;↵
}↵
↵
pair<int, ll> LA(int v, int k) {↵
if (k <= 0) return {v, 0};↵
ll sum = 0;↵
for (int i = 0; i < 20; ++i) {↵
if (k >> i & 1) sum += up[i][v].second, v = up[i][v].first;↵
}↵
return {v, sum};↵
}↵
↵
int LCA(int u, int v) {↵
if (anc(u, v)) return u;↵
for (int l = 19; l >= 0; --l) {↵
if (up[l][u].first == -1 || anc(up[l][u].first, v)) continue;↵
u = up[l][u].first;↵
}↵
return up[0][u].first;↵
}↵
↵
bool lower(int a, int b) {↵
return tin[a] < tin[b];↵
}↵
};↵
↵
ll sum(int r) { return r * 1ll * (r + 1) / 2; }↵
↵
ll sumSeg(int l, int r) {↵
return sum(r) - sum(l - 1);↵
}↵
↵
void solve() {↵
int n, q; cin >> n >> q;↵
vector<int> a(n);↵
for (int i = 0; i < n; ++i) cin >> a[i];↵
vector<vector<int>> g(n);↵
for (int i = 1; i < n; ++i) {↵
int u, v; cin >> u >> v;↵
--u, --v;↵
g[u].emplace_back(v);↵
g[v].emplace_back(u);↵
}↵
vector<int> parent(n), d(n);↵
auto dfs = [&](auto& self, int v, int p = -1) -> void {↵
parent[v] = p;↵
for (int u : g[v]) {↵
if (u == p) continue;↵
d[u] = d[v] + 1;↵
self(self, u, v);↵
}↵
};↵
dfs(dfs, 0);↵
↵
vector<int> compressed_parent = parent;↵
vector<vector<int>> cG(n);↵
for (int v = 0; v < n; ++v) {↵
vector<int> path;↵
while (compressed_parent[v] > 0 && a[compressed_parent[v]] == 0) {↵
path.emplace_back(compressed_parent[v]);↵
compressed_parent[v] = compressed_parent[compressed_parent[v]];↵
}↵
for (auto& x : path) compressed_parent[x] = compressed_parent[v];↵
if (a[v] == 0 || !v) continue;↵
cG[compressed_parent[v]].emplace_back(v);↵
}↵
↵
vector<int> next_collision(n), sum_collision(n);↵
for (int v = 0; v < n; ++v) {↵
if (!a[v]) continue;↵
next_collision[v] = v;↵
int xr = a[v], sm = a[v];↵
while (xr == sm && next_collision[v] > -1) {↵
next_collision[v] = compressed_parent[next_collision[v]];↵
if (next_collision[v] == -1) break;↵
xr ^= a[next_collision[v]];↵
sm += a[next_collision[v]];↵
}↵
}↵
↵
for (int v = 0; v < n; ++v) {↵
if (!a[v]) {↵
if (!v) next_collision[v] = -1;↵
else next_collision[v] = next_collision[compressed_parent[v]];↵
}↵
sum_collision[v] = d[v];↵
if (next_collision[v] > -1) sum_collision[v] -= d[next_collision[v]];↵
else sum_collision[v]++;↵
}↵
↵
Graph def(g, sum_collision);↵
Graph compressed(cG, sum_collision);↵
↵
while (q--) {↵
int u, v; cin >> u >> v;↵
--u, --v;↵
if (def.lower(v, u)) swap(u, v);↵
int z = def.LCA(u, v);↵
↵
int cv = (a[v] || !v ? v : compressed_parent[v]), cu = (a[u] || !u ? u : compressed_parent[u]), cz = (a[z] || !z ? z : compressed_parent[z]);↵
↵
ll ans = 0;↵
↵
vector<int> L, R, Lspaces = {0}, Rspaces = {0};↵
↵
if (compressed.d[cv] > compressed.d[cz] + 23) {↵
int unt = compressed.LA(cv, compressed.d[cv] - (compressed.d[cz] + 23)).first;↵
auto [to, sm] = def.LA(v, d[v] - d[unt]);↵
ans += sm, v = to;↵
}↵
↵
if (compressed.d[cu] > compressed.d[cz] + 23) {↵
int unt = compressed.LA(cu, compressed.d[cu] - (compressed.d[cz] + 23)).first;↵
auto [to, sm] = def.LA(u, d[u] - d[unt]);↵
ans += sm, u = to;↵
}↵
↵
while (u != z) {↵
int to = compressed_parent[u];↵
if (def.anc(to, z)) to = z;↵
L.emplace_back(u);↵
Lspaces.emplace_back(def.getLenVertical(u, to));↵
u = to;↵
}↵
while (v != z) {↵
int to = compressed_parent[v];↵
if (def.anc(to, z)) to = z;↵
R.emplace_back(v);↵
Rspaces.emplace_back(def.getLenVertical(v, to));↵
v = to;↵
}↵
L.emplace_back(z);↵
std::reverse(R.begin(), R.end());↵
std::reverse(Rspaces.begin(), Rspaces.end());↵
for (auto& x : R) L.emplace_back(x);↵
for (auto& x : Rspaces) Lspaces.emplace_back(x);↵
int j = 0, xr = 0, sum = 0;↵
ll cnt = 0;↵
for (int i = 0; i < L.size(); ++i) {↵
while (j < L.size() && xr == sum) {↵
xr ^= a[L[j]], sum += a[L[j]];↵
cnt += Lspaces[j] + 1;↵
j++;↵
}↵
if (xr != sum) cnt--;↵
ans += sumSeg(cnt - Lspaces[i], cnt);↵
if (xr != sum) cnt++;↵
xr ^= a[L[i]], sum -= a[L[i]];↵
cnt -= Lspaces[i] + 1;↵
}↵
cout << ans << '\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Solution 2 (Treks)">↵
~~~~~↵
//#pragma GCC optimize("Ofast")↵
//#pragma GCC optimize("O3,unroll-loops")↵
↵
#include <bits/stdc++.h>↵
#include <experimental/random>↵
#include <ext/pb_ds/assoc_container.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
using ll = long long;↵
using ld = long double;↵
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;↵
using str = string;↵
const ll INF = 1e18, MOD = 1e9 + 7;↵
template<class T> using pq_min = priority_queue<T, vector<T>, greater<T>>;↵
template<class T> using pq_max = priority_queue<T, vector<T>, less<T>>;↵
#define int long long↵
↵
void solve();↵
↵
signed main() {↵
#ifdef LOCAL↵
freopen("input.txt", "r", stdin);↵
freopen("output.txt", "w", stdout);↵
#endif↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
ll q = 1;↵
cin >> q;↵
while (q--) {↵
solve();↵
//cout << "\n";↵
}↵
}↵
↵
vector<vector<int>> g;↵
vector<int> a;↵
int h;↵
vector<bool> us;↵
int cnt1;↵
vector<int> T;↵
↵
void dfs1(int v, int pr) {↵
T.push_back(v);↵
cnt1++;↵
for (auto to: g[v]) {↵
if (to != pr && !us[to]) {↵
dfs1(to, v);↵
}↵
}↵
}↵
↵
int dfs(int v, int pr) {↵
bool p = true;↵
int cnt = 1;↵
for (auto to: g[v]) {↵
if (to != pr && !us[to]) {↵
auto u = dfs(to, v);↵
if (u > cnt1 / 2) {↵
p = false;↵
}↵
cnt += u;↵
}↵
}↵
if (p && (cnt1 — cnt) <= cnt1 / 2) {↵
h = v;↵
}↵
return cnt;↵
}↵
↵
int E = 0;↵
↵
vector<int> ans;↵
vector<vector<int>> mn;↵
vector<int> col;↵
vector<int> sz;↵
vector<int> W;↵
↵
void dfs(int v, int pr, vector<int> s, int an, int o, int mx) {↵
sz[v] = o;↵
col[v] = E;↵
W[v] = W[pr];↵
for (int i = 0; i < 20; ++i) { ↵
mn[v][i] = mn[pr][i];↵
}↵
for (int i = 0; i < 20; ++i) {↵
if ((a[v] >> i) & 1) {↵
if (mn[v][i] != INF) {↵
W[v] = min(W[v], o);↵
}↵
mn[v][i] = min(mn[v][i], o);↵
mx = max(mx, s[i]);↵
s[i] = o;↵
}↵
}↵
an += o — mx;↵
ans[v] = an;↵
for (auto to: g[v]) {↵
if (to != pr && !us[to]) {↵
dfs(to, v, s, an, o + 1, mx);↵
}↵
}↵
}↵
↵
vector<vector<pair<int, int>>> que;↵
vector<int> ANS;↵
↵
void rec(int v) {↵
T.clear();↵
cnt1 = 0;↵
dfs1(v, -1);↵
dfs(v, -1);↵
v = h;↵
us[v] = true;↵
mn[v] = vector<int>(20, INF);↵
int S = E;↵
W[v] = INF;↵
for (auto to: g[v]) {↵
if (!us[to]) {↵
E++;↵
vector<int> s(20, 0);↵
dfs(to, v, s, 0, 1, 0);↵
}↵
}↵
ans[v] = 0;↵
++E;↵
col[v] = E;↵
for (auto x: T) {↵
for (auto [y, id]: que[x]) {↵
if (col[x] != col[y] && col[x] > S && col[y] > S) {↵
ANS[id] = ans[x] + ans[y];↵
if (x == v) {↵
int MN = min(W[y], sz[y] + 1);↵
for (int i = 0; i < 20; ++i) {↵
if ((a[v] >> i) & 1) {↵
MN = min(MN, mn[y][i]);↵
}↵
}↵
ANS[id] += MN;↵
} else if (y == v) {↵
int MN = min(W[x], sz[x] + 1);↵
for (int i = 0; i < 20; ++i) {↵
if ((a[v] >> i) & 1) {↵
MN = min(MN, mn[x][i]);↵
}↵
}↵
ANS[id] += MN;↵
} else {↵
vector<pair<int, int>> upd;↵
for (int i = 0; i < 20; ++i) {↵
if (mn[x][i] != INF) {↵
upd.push_back({mn[x][i], i});↵
}↵
}↵
int e = min(W[y], sz[y] + 1);↵
for (int i = 0; i < 20; ++i) {↵
if ((a[v] >> i) & 1) {↵
e = min(e, mn[y][i]);↵
}↵
}↵
sort(upd.begin(), upd.end());↵
int p = 0;↵
bool flag = true;↵
for (int i = 0; i < upd.size(); ++i) {↵
if (upd[i].first >= W[x]) {↵
ANS[id] += (W[x] — p) * e;↵
flag = false;↵
break;↵
}↵
ANS[id] += (upd[i].first — p) * e;↵
if ((a[v] >> upd[i].second) & 1) {↵
flag = false;↵
break;↵
}↵
e = min(e, mn[y][upd[i].second]);↵
p = upd[i].first;↵
}↵
if (flag) {↵
ANS[id] += (min(W[x], sz[x] + 1) — p) * e;↵
}↵
}↵
}↵
}↵
}↵
for (int i = 0; i < g[v].size(); ++i) {↵
int to = g[v][i];↵
if (!us[to]) {↵
rec(to);↵
}↵
}↵
}↵
↵
↵
void solve() {↵
int n, q;↵
cin >> n >> q;↵
sz.clear();↵
W.clear();↵
W.resize(n);↵
sz.resize(n);↵
ans.clear();↵
ANS.clear();↵
ANS.resize(q, -1);↵
mn.clear();↵
ans.resize(n);↵
mn.resize(n, vector<int>(20));↵
a.clear();↵
us.clear();↵
us.resize(n);↵
a.resize(n);↵
for (int i = 0; i < n; ++i) {↵
cin >> a[i];↵
}↵
g.clear();↵
col.clear();↵
col.resize(n);↵
que.clear();↵
que.resize(n);↵
g.resize(n);↵
for (int i = 0; i < n — 1; ++i) {↵
int u, v;↵
cin >> u >> v;↵
--u;↵
--v;↵
g[u].push_back(v);↵
g[v].push_back(u);↵
}↵
for (int i = 0; i < q; ++i) {↵
int x, y;↵
cin >> x >> y;↵
--x;↵
--y;↵
que[x].push_back({y, i});↵
}↵
rec(0);↵
for (int i = 0; i < q; ++i) {↵
if (ANS[i] == -1) {↵
exit(-1);↵
}↵
cout << ANS[i] << "\n";↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
Idea: [user:arsen1y,2026-06-13]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2236A]↵
</spoiler>↵
↵
<spoiler summary="Solution (arsen1y)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define int long long↵
↵
using namespace std;↵
↵
const int INF = (int) 1e18;↵
↵
int32_t main() {↵
std::ios::sync_with_stdio(false);↵
cin.tie(NULL);↵
cout.tie(NULL);↵
↵
int _;↵
cin >> _;↵
↵
while (_--) {↵
int n;↵
cin >> n;↵
↵
vector <int> a(n);↵
int mx = -INF;↵
int mn = INF;↵
for (int i = 0; i < n; ++i) {↵
cin >> a[i];↵
mx = max(mx, a[i]);↵
mn = min(mn, a[i]);↵
}↵
↵
cout << mx - mn + 1 << "\n";↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2236B]↵
↵
Idea: [user:eyfxrby,2026-06-13]↵
↵
<spoiler summary="Hint">↵
Try to find a property that does not change during operations.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2236B]↵
</spoiler>↵
↵
<spoiler summary="Solution (eyfxrby)">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
int t;↵
cin >> t;↵
while (t--) {↵
int n, k; cin >> n >> k;↵
string s; cin >> s;↵
vector<int> cnt(k, 0);↵
for (int i = 0; i < n; i++) cnt[i % k] += s[i] - '0';↵
bool ok = true;↵
for (int r = 0; r < k; r++) {↵
if (cnt[r] % 2) {↵
ok = false;↵
break;↵
}↵
}↵
cout << (ok ? "YES" : "NO") << '\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2236C]↵
↵
Idea: [user:arsen1y,2026-06-13]↵
↵
<spoiler summary="Hint">↵
It can be shown that it is advantageous to do only divisions first, and then only additions.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2236C]↵
</spoiler>↵
↵
<spoiler summary="Solution (arsen1y)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#define int long long↵
↵
using namespace std;↵
↵
const int INF = (int) 1e18;↵
↵
int32_t main() {↵
int _;↵
cin >> _;↵
↵
while (_--) {↵
int a, b, x;↵
cin >> a >> b >> x;↵
↵
int ans = INF;↵
int i = 0;↵
while (a != b) {↵
if (b > a) {↵
swap(a, b);↵
}↵
↵
ans = min(ans, abs(a - b) + i);↵
a /= x;↵
i++;↵
}↵
↵
ans = min(ans, i);↵
↵
cout << ans << "\n";↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2236D]↵
↵
Idea: [user:dvb1r,2026-06-13]↵
↵
<spoiler summary="Hint 1">↵
What happens if Arseny chooses the maximum of the array as his first move?↵
↵
<spoiler summary="Answer">↵
If the count of maximum is odd, then Dabir wins, otherwise Egor wins.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Try to look at the second maximum.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2236D]↵
</spoiler>↵
↵
<spoiler summary="Solution (dvb1r)">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
void solve();↵
↵
int main() {↵
int t; cin >> t;↵
while (t--) solve();↵
return 0;↵
}↵
↵
void solve() {↵
int n, k; cin >> n >> k;↵
vector<int> A(n);↵
for (auto& x : A) cin >> x;↵
sort(A.begin(), A.end());↵
vector<pair<int, int>> a = {{A[0], 1}};↵
for (int i = 1; i < n; ++i) {↵
if (A[i] == A[i - 1]) a.back().second++;↵
else a.emplace_back(A[i], 1);↵
}↵
↵
while (a.size() > 0) {↵
n = a.size();↵
if (a[n - 1].second % 2 == 0) {↵
cout << "YES\n";↵
return;↵
}↵
if (n == 1) {↵
cout << "NO\n";↵
return;↵
}↵
if (a[n - 1].first - a[n - 2].first <= k) {↵
cout << "YES\n";↵
return;↵
}↵
a.pop_back();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2236E]↵
↵
Idea: [user:arsen1y,2026-06-13]↵
↵
<spoiler summary="Hint 1">↵
The cut segments of the array do not need to be checked for non-intersection.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Try to save information about all the good segments, and only then find the answer.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2236E]↵
</spoiler>↵
↵
<spoiler summary="Solution (dvb1r)">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
void solve();↵
↵
int main() {↵
int t = 1; cin >> t;↵
while (t--) solve();↵
return 0;↵
}↵
↵
void solve() {↵
int n; cin >> n;↵
vector<int> a(n);↵
for (auto& x : a) cin >> x, --x;↵
vector<vector<bool>> able(n, vector<bool>(n));↵
for (int i = 0; i < n; ++i) {↵
vector<int> us(n);↵
int mn = a[i], mx = a[i];↵
for (int j = i; j < n; ++j) {↵
if (us[a[j]]) break;↵
us[a[j]] = 1;↵
mn = min(mn, a[j]), mx = max(mx, a[j]);↵
if (mx - mn == j - i) able[mn][mx] = 1;↵
}↵
}↵
↵
for (int ans = n; ans > 0; --ans) {↵
for (int i = 0; i + 2 * ans <= n; ++i) {↵
if (able[i][i + ans - 1] && able[i + ans][i + 2 * ans - 1]) {↵
cout << ans << '\n';↵
return;↵
}↵
}↵
}↵
cout << "0\n";↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2236F1]↵
↵
Idea: [user:eyfxrby,2026-06-13]↵
↵
<spoiler summary="Hint 1">↵
What can we say about $gcd(p_i, p_j)$ for any pair $(i, j)$?↵
↵
<spoiler summary="Ответ">↵
$gcd(p_i, p_j) = 1$.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Let's take a simple number $pr$. How many elements of the array $p$ can be divisible by this $pr$?↵
↵
<spoiler summary="Ответ">↵
No more than one.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2236F1]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <bits/stdc++.h>↵
#include <immintrin.h>↵
↵
using namespace __gnu_pbds;↵
using namespace std;↵
↵
#define eps 1e-7↵
#define MOD2 119 * (1ll << 23) + 1↵
#define int long long↵
#define mp make_pair↵
#define pll pair <long long, long long>↵
#define next return↵
#define skip continue↵
#define all(a) a.begin(), a.end()↵
#define rall(a) a.rbegin(), a.rend()↵
#define f first↵
#define max_of max_element↵
#define min_of min_element↵
#define s second↵
↵
// const int MAX_MEM = 4e8;↵
// int mpos = 0;↵
// alignas(long long) char mem[MAX_MEM];↵
// inline void * operator new(size_t n) {↵
// if (n & 7) n += 8 - (n & 7);↵
// char *res = mem + mpos;↵
// mpos += n;↵
// return (void *)res;↵
// }↵
// void operator delete(void *) {}↵
↵
int scan() {↵
int x;↵
cin >> x;↵
return x;↵
}↵
↵
string read() {↵
string s;↵
cin >> s;↵
return s;↵
}↵
↵
const int N = 1e6 + 5, MOD = 1e9 + 7;↵
int lp[N], a[N], x, n, v[101];↵
vector<int> pr, divs[N];↵
↵
int bin_pow(int x, int n) {↵
int res = 1;↵
while (n) {↵
if ((n & 1)) res = res * x % MOD;↵
n >>= 1;↵
x = x * x % MOD;↵
}↵
return res;↵
}↵
↵
int solveF1_AUTHOR() {↵
map <int, int> cnt;↵
int cur_x;↵
int mx = *max_element(a + 1, a + n + 1);↵
set <int> setik;↵
for (int i = 1; i <= n; i++) {↵
int val = a[i];↵
cur_x = val;↵
while (cur_x > 1) {↵
setik.insert(lp[cur_x]);↵
cnt[lp[cur_x]]++;↵
cur_x /= lp[cur_x];↵
}↵
}↵
int ans = 1;↵
for (auto prime: setik) {↵
int sum = 1;↵
//cout << prime << ' ' << cnt[prime] << '\n';↵
ans = (ans * (cnt[prime] + 1)) % MOD;↵
}↵
return ans;↵
}↵
↵
↵
int32_t main() {↵
lp[1] = 1;↵
for (int i = 2; i < N; i++) {↵
if (lp[i] == 0) {↵
pr.push_back(i);↵
lp[i] = i;↵
}↵
for (int j = 0; j < (int) pr.size() && pr[j] <= lp[i] && i * pr[j] < N; j++) {↵
lp[i * pr[j]] = pr[j];↵
}↵
}↵
int t = scan();↵
while (t--) {↵
n = scan(); x = scan();↵
for (int i = 1; i <= n; i++) a[i] = scan();↵
cout << solveF1_AUTHOR() << '\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2236F2]↵
↵
Idea: [user:eyfxrby,2026-06-13]↵
↵
<spoiler summary="Hint 1">↵
Try to fix the prime number $pr$. How can we transform the condition of the perfect array $p$ using $v_{pr}$?↵
↵
<spoiler summary="Answer">↵
$x \cdot lcm(p_1, p_2, \ldots, p_n) = p_1 \cdot p_2 * \ldots \cdot p_n <=> max(v_{pr}(p_i)) + v_{pr}(x) = \sum(v_{pr}(p_i)$)↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider what a simple $pr$ might be. What types of $pr$ can it be classified into?↵
↵
<spoiler summary="Answer">↵
$x$ is divisible by $pr$, and $x$ is not divisible by $pr$.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Think about how to solve each of the cases in hint 2.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2236F2]↵
</spoiler>↵
↵
<spoiler summary="Solution 1 (eyfxrby)">↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <bits/stdc++.h>↵
#include <immintrin.h>↵
↵
using namespace __gnu_pbds;↵
using namespace std;↵
↵
#define eps 1e-7↵
#define MOD2 119 * (1ll << 23) + 1↵
#define int long long↵
#define mp make_pair↵
#define pll pair <long long, long long>↵
#define next return↵
#define skip continue↵
#define all(a) a.begin(), a.end()↵
#define rall(a) a.rbegin(), a.rend()↵
#define f first↵
#define max_of max_element↵
#define min_of min_element↵
#define s second↵
↵
int scan() {↵
int x;↵
cin >> x;↵
return x;↵
}↵
↵
string read() {↵
string s;↵
cin >> s;↵
return s;↵
}↵
↵
const int N = 1e6 + 2, MOD = 1e9 + 7;↵
int lp[N], a[N], x, n, v[N];↵
vector<int> pr, divs[N];↵
↵
int MAX_V = -1E9;↵
↵
int solve_for_prime(int vp) {↵
int mx_pref = 0;↵
int S = 0;↵
for (int i = 1; i <= n; i++) S += v[i];↵
S = min(S, 36ll);↵
int dp[MAX_V + 1][MAX_V + S + 2];↵
int old_pref_sum[MAX_V + 1][MAX_V + S + 2];↵
int old_pref_sum2[MAX_V + 1][MAX_V + S + 2];↵
memset(dp, 0, sizeof dp);↵
memset(old_pref_sum, 0, sizeof old_pref_sum);↵
memset(old_pref_sum2, 0, sizeof old_pref_sum2);↵
int sum = 0;↵
dp[0][0] = 1;↵
for (int i = 0; i <= n; i++) {↵
for (int sum_vp = 0; sum_vp <= S && i > 0; sum_vp++) {↵
for (int new_max = 1; new_max <= min(sum_vp, v[i]); new_max++) {↵
dp[new_max][sum_vp] += old_pref_sum2[new_max - 1][sum_vp - new_max];↵
if (dp[new_max][sum_vp] >= MOD) dp[new_max][sum_vp] -= MOD;↵
}↵
for (int old_max = 0; old_max <= min(mx_pref, sum_vp); old_max++) {↵
dp[old_max][sum_vp] += (old_pref_sum[old_max][sum_vp] + MOD - (sum_vp - min(old_max, v[i]) - 1 < 0 ? 0 :↵
old_pref_sum[old_max][sum_vp - min(old_max, v[i]) - 1])) % MOD;↵
//if (dp[old_max][sum_vp] >= MOD) dp[old_max][sum_vp] -= MOD;↵
↵
}↵
}↵
for (int old_max = 0; old_max <= MAX_V; old_max++) {↵
for (int j = 0; j <= MAX_V + S; j++) {↵
old_pref_sum[old_max][j] = 0;↵
old_pref_sum[old_max][j] = (!j ? dp[old_max][j] : old_pref_sum[old_max][j - 1] + dp[old_max][j]);↵
if (old_pref_sum[old_max][j] >= MOD) old_pref_sum[old_max][j] -= MOD;↵
}↵
}↵
for (int j = 0; j <= MAX_V + S; j++) {↵
for (int old_max = 0; old_max <= MAX_V; old_max++) {↵
old_pref_sum2[old_max][j] = 0;↵
old_pref_sum2[old_max][j] = (!old_max ? dp[old_max][j] : old_pref_sum2[old_max - 1][j] + dp[old_max][j]);↵
if (old_pref_sum2[old_max][j] >= MOD) old_pref_sum2[old_max][j] -= MOD;↵
if(i != n) dp[old_max][j] = 0;↵
}↵
}↵
mx_pref = max(mx_pref, v[i]);↵
}↵
int ret = 0;↵
for (int mx = 1; vp + mx <= S && mx <= MAX_V; mx++) {↵
ret = (ret + dp[mx][vp + mx]);↵
if (ret >= MOD) ret -= MOD;↵
}↵
return ret;↵
}↵
↵
int solveF2_AUTHOR() {↵
map<int, int> cnt_pr;↵
int cur_x = x;↵
while (cur_x > 1) {↵
int next_div = lp[cur_x];↵
cnt_pr[next_div]++;↵
cur_x /= next_div;↵
}↵
int ans = 1;↵
for (auto [prime, cnt]: cnt_pr) {↵
MAX_V = -1e9;↵
for (int i = 1; i <= n; i++) {↵
cur_x = a[i];↵
v[i] = 0;↵
while (cur_x % prime == 0) {↵
v[i]++;↵
cur_x /= prime;↵
}↵
MAX_V = max(MAX_V, v[i]);↵
}↵
ans = (ans * solve_for_prime(cnt)) % MOD;↵
}↵
map <int, int> cnt;↵
int mx = *max_element(a + 1, a + n + 1);↵
set <int> setik;↵
for (int i = 1; i <= n; i++) {↵
int val = a[i];↵
cur_x = val;↵
while (cur_x > 1) {↵
cnt[lp[cur_x]]++;↵
setik.insert(lp[cur_x]);↵
cur_x /= lp[cur_x];↵
}↵
}↵
for (auto prime: setik) {↵
//if (2 * prime > mx) break;↵
int sum = 1;↵
if (x % prime != 0) ans = (ans * (cnt[prime] + 1)) % MOD;↵
}↵
return ans;↵
}↵
↵
↵
int32_t main() {↵
for (int i = 2; i < N; i++) {↵
if (lp[i] == 0) {↵
pr.push_back(i);↵
lp[i] = i;↵
}↵
for (int j = 0; j < (int) pr.size() && pr[j] <= lp[i] && i * pr[j] < N; j++) {↵
lp[i * pr[j]] = pr[j];↵
}↵
}↵
int t = scan();↵
while (t--) {↵
n = scan(), x = scan();↵
for (int i = 1; i <= n; i++) a[i] = scan();↵
cout << solveF2_AUTHOR() << '\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Solution 2 (Treks)">↵
~~~~~↵
//#pragma GCC optimize("Ofast")↵
//#pragma GCC optimize("O3,unroll-loops")↵
↵
#include <bits/stdc++.h>↵
#include <experimental/random>↵
#include <ext/pb_ds/assoc_container.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
using ll = long long;↵
using ld = long double;↵
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;↵
using str = string;↵
const ll INF = 1e18, MOD = 1e9 + 7;↵
template<class T> using pq_min = priority_queue<T, vector<T>, greater<T>>;↵
template<class T> using pq_max = priority_queue<T, vector<T>, less<T>>;↵
#define int long long↵
↵
void solve();↵
↵
vector<int> P;↵
const int Mx = 1e4;↵
↵
signed main() {↵
vector<bool> us(Mx);↵
for (int i = 2; i < Mx; ++i) {↵
if (!us[i]) {↵
P.push_back(i);↵
for (int j = i * i; j < Mx; j += i) {↵
us[j] = true;↵
}↵
}↵
}↵
#ifdef LOCAL↵
freopen("input.txt", "r", stdin);↵
freopen("output.txt", "w", stdout);↵
#endif↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
ll q = 1;↵
cin >> q;↵
while (q--) {↵
solve();↵
cout << "\n";↵
}↵
}↵
↵
void solve() {↵
int n, x;↵
cin >> n >> x;↵
map<int, int> cnt;↵
for (auto w: P) {↵
if (w * w > x) {↵
break;↵
}↵
while (x % w == 0) {↵
x /= w;↵
cnt[w]++;↵
}↵
}↵
if (x > 1) {↵
cnt[x]++;↵
}↵
vector<int> a(n);↵
for (int i = 0; i < n; ++i) {↵
cin >> a[i];↵
}↵
map<int, vector<int>> w1;↵
for (int i = 0; i < n; ++i) {↵
for (auto w: P) {↵
if (w * w > a[i]) {↵
break;↵
}↵
int sum = 0;↵
while (a[i] % w == 0) {↵
a[i] /= w;↵
sum++;↵
}↵
if (sum > 0) {↵
w1[w].push_back(sum);↵
}↵
}↵
if (a[i] > 1) {↵
w1[a[i]].push_back(1);↵
}↵
}↵
int Ans = 1;↵
for (auto [id, e]: w1) {↵
int mx = 0;↵
for (auto s: e) {↵
mx = max(mx, s);↵
}↵
vector<vector<int>> dp(cnt[id] + 1, vector<int>(mx + 1));↵
dp[0][0] = 1;↵
for (auto w: e) {↵
vector<vector<int>> dp1(cnt[id] + 1, vector<int>(mx + 1));↵
for (int i = 0; i <= w; ++i) {↵
for (int j = 0; j <= cnt[id]; ++j) {↵
for (int k = 0; k <= mx; ++k) {↵
if (j + min(i, k) <= cnt[id]) {↵
dp1[j + min(i, k)][max(i, k)] += dp[j][k];↵
dp1[j + min(i, k)][max(i, k)] %= MOD;↵
}↵
}↵
}↵
}↵
swap(dp, dp1);↵
}↵
int s = 0;↵
for (int i = 0; i <= mx; ++i) {↵
s += dp[cnt[id]][i];↵
}↵
s %= MOD;↵
Ans *= s;↵
Ans %= MOD;↵
cnt[id] = 0;↵
}↵
for (auto s: cnt) {↵
if (s.second > 0) {↵
Ans = 0;↵
}↵
}↵
cout << Ans;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2236G]↵
↵
Idea: [user:dvb1r,2026-06-13]↵
↵
<spoiler summary="Hint 1">↵
In fact, the XOR of non-negative numbers is always less or equal their sum, and you can think about why.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Using the fact that the XOR of a set of numbers is equal to the sum of those numbers, how many non-zero numbers can there be in this set?↵
↵
<spoiler summary="Answer">↵
No more than $log(A)$, since each bit must occur at most once.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
For each vertex, pre-calculate the closest ancestor on the vertical path that violates the good segment condition.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Reduce the problem to a path of length at most $2 * log(A)$, and calculate the rest using the pre-calculation from hint 3.↵
</spoiler>↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2236G]↵
</spoiler>↵
↵
<spoiler summary="Solution 1 (dvb1r)">↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
using ll = long long;↵
void solve();↵
↵
int main() {↵
int t = 1;↵
cin >> t;↵
while (t --> 0) solve();↵
return 0;↵
}↵
↵
struct Graph {↵
vector<int> tin, tout, d;↵
vector<vector<pair<int, ll>>> up;↵
↵
int timer;↵
↵
void dfs(int v, const vector<vector<int>>& g, const vector<int>& arr, int p = -1) {↵
tin[v] = timer++;↵
up[0][v] = {p, arr[v]};↵
for (int l = 1; l < 20; ++l) {↵
if (up[l - 1][v].first == -1) {↵
up[l][v] = {-1, 0};↵
continue;↵
}↵
up[l][v].first = up[l - 1][up[l - 1][v].first].first;↵
up[l][v].second = up[l - 1][up[l - 1][v].first].second + up[l - 1][v].second;↵
}↵
for (int u : g[v]) {↵
if (u == p) continue;↵
d[u] = d[v] + 1;↵
dfs(u, g, arr, v);↵
}↵
tout[v] = timer;↵
}↵
↵
Graph(const vector<vector<int>>& g, const vector<int>& a) : tin(g.size()), tout(g.size()), d(g.size()), up(20, vector<pair<int, ll>>(g.size())) {↵
timer = 0;↵
dfs(0, g, a);↵
}↵
↵
bool anc(int p, int v) {↵
return tin[p] <= tin[v] && tout[p] >= tout[v];↵
}↵
↵
int getLenVertical(int u, int v) {↵
if (!anc(u, v)) swap(u, v);↵
assert(anc(u, v));↵
return d[v] - d[u] - 1;↵
}↵
↵
pair<int, ll> LA(int v, int k) {↵
if (k <= 0) return {v, 0};↵
ll sum = 0;↵
for (int i = 0; i < 20; ++i) {↵
if (k >> i & 1) sum += up[i][v].second, v = up[i][v].first;↵
}↵
return {v, sum};↵
}↵
↵
int LCA(int u, int v) {↵
if (anc(u, v)) return u;↵
for (int l = 19; l >= 0; --l) {↵
if (up[l][u].first == -1 || anc(up[l][u].first, v)) continue;↵
u = up[l][u].first;↵
}↵
return up[0][u].first;↵
}↵
↵
bool lower(int a, int b) {↵
return tin[a] < tin[b];↵
}↵
};↵
↵
ll sum(int r) { return r * 1ll * (r + 1) / 2; }↵
↵
ll sumSeg(int l, int r) {↵
return sum(r) - sum(l - 1);↵
}↵
↵
void solve() {↵
int n, q; cin >> n >> q;↵
vector<int> a(n);↵
for (int i = 0; i < n; ++i) cin >> a[i];↵
vector<vector<int>> g(n);↵
for (int i = 1; i < n; ++i) {↵
int u, v; cin >> u >> v;↵
--u, --v;↵
g[u].emplace_back(v);↵
g[v].emplace_back(u);↵
}↵
vector<int> parent(n), d(n);↵
auto dfs = [&](auto& self, int v, int p = -1) -> void {↵
parent[v] = p;↵
for (int u : g[v]) {↵
if (u == p) continue;↵
d[u] = d[v] + 1;↵
self(self, u, v);↵
}↵
};↵
dfs(dfs, 0);↵
↵
vector<int> compressed_parent = parent;↵
vector<vector<int>> cG(n);↵
for (int v = 0; v < n; ++v) {↵
vector<int> path;↵
while (compressed_parent[v] > 0 && a[compressed_parent[v]] == 0) {↵
path.emplace_back(compressed_parent[v]);↵
compressed_parent[v] = compressed_parent[compressed_parent[v]];↵
}↵
for (auto& x : path) compressed_parent[x] = compressed_parent[v];↵
if (a[v] == 0 || !v) continue;↵
cG[compressed_parent[v]].emplace_back(v);↵
}↵
↵
vector<int> next_collision(n), sum_collision(n);↵
for (int v = 0; v < n; ++v) {↵
if (!a[v]) continue;↵
next_collision[v] = v;↵
int xr = a[v], sm = a[v];↵
while (xr == sm && next_collision[v] > -1) {↵
next_collision[v] = compressed_parent[next_collision[v]];↵
if (next_collision[v] == -1) break;↵
xr ^= a[next_collision[v]];↵
sm += a[next_collision[v]];↵
}↵
}↵
↵
for (int v = 0; v < n; ++v) {↵
if (!a[v]) {↵
if (!v) next_collision[v] = -1;↵
else next_collision[v] = next_collision[compressed_parent[v]];↵
}↵
sum_collision[v] = d[v];↵
if (next_collision[v] > -1) sum_collision[v] -= d[next_collision[v]];↵
else sum_collision[v]++;↵
}↵
↵
Graph def(g, sum_collision);↵
Graph compressed(cG, sum_collision);↵
↵
while (q--) {↵
int u, v; cin >> u >> v;↵
--u, --v;↵
if (def.lower(v, u)) swap(u, v);↵
int z = def.LCA(u, v);↵
↵
int cv = (a[v] || !v ? v : compressed_parent[v]), cu = (a[u] || !u ? u : compressed_parent[u]), cz = (a[z] || !z ? z : compressed_parent[z]);↵
↵
ll ans = 0;↵
↵
vector<int> L, R, Lspaces = {0}, Rspaces = {0};↵
↵
if (compressed.d[cv] > compressed.d[cz] + 23) {↵
int unt = compressed.LA(cv, compressed.d[cv] - (compressed.d[cz] + 23)).first;↵
auto [to, sm] = def.LA(v, d[v] - d[unt]);↵
ans += sm, v = to;↵
}↵
↵
if (compressed.d[cu] > compressed.d[cz] + 23) {↵
int unt = compressed.LA(cu, compressed.d[cu] - (compressed.d[cz] + 23)).first;↵
auto [to, sm] = def.LA(u, d[u] - d[unt]);↵
ans += sm, u = to;↵
}↵
↵
while (u != z) {↵
int to = compressed_parent[u];↵
if (def.anc(to, z)) to = z;↵
L.emplace_back(u);↵
Lspaces.emplace_back(def.getLenVertical(u, to));↵
u = to;↵
}↵
while (v != z) {↵
int to = compressed_parent[v];↵
if (def.anc(to, z)) to = z;↵
R.emplace_back(v);↵
Rspaces.emplace_back(def.getLenVertical(v, to));↵
v = to;↵
}↵
L.emplace_back(z);↵
std::reverse(R.begin(), R.end());↵
std::reverse(Rspaces.begin(), Rspaces.end());↵
for (auto& x : R) L.emplace_back(x);↵
for (auto& x : Rspaces) Lspaces.emplace_back(x);↵
int j = 0, xr = 0, sum = 0;↵
ll cnt = 0;↵
for (int i = 0; i < L.size(); ++i) {↵
while (j < L.size() && xr == sum) {↵
xr ^= a[L[j]], sum += a[L[j]];↵
cnt += Lspaces[j] + 1;↵
j++;↵
}↵
if (xr != sum) cnt--;↵
ans += sumSeg(cnt - Lspaces[i], cnt);↵
if (xr != sum) cnt++;↵
xr ^= a[L[i]], sum -= a[L[i]];↵
cnt -= Lspaces[i] + 1;↵
}↵
cout << ans << '\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
<spoiler summary="Solution 2 (Treks)">↵
~~~~~↵
//#pragma GCC optimize("Ofast")↵
//#pragma GCC optimize("O3,unroll-loops")↵
↵
#include <bits/stdc++.h>↵
#include <experimental/random>↵
#include <ext/pb_ds/assoc_container.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
using ll = long long;↵
using ld = long double;↵
using ordered_set = tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>;↵
using str = string;↵
const ll INF = 1e18, MOD = 1e9 + 7;↵
template<class T> using pq_min = priority_queue<T, vector<T>, greater<T>>;↵
template<class T> using pq_max = priority_queue<T, vector<T>, less<T>>;↵
#define int long long↵
↵
void solve();↵
↵
signed main() {↵
#ifdef LOCAL↵
freopen("input.txt", "r", stdin);↵
freopen("output.txt", "w", stdout);↵
#endif↵
ios::sync_with_stdio(false);↵
cin.tie(0);↵
cout.tie(0);↵
ll q = 1;↵
cin >> q;↵
while (q--) {↵
solve();↵
//cout << "\n";↵
}↵
}↵
↵
vector<vector<int>> g;↵
vector<int> a;↵
int h;↵
vector<bool> us;↵
int cnt1;↵
vector<int> T;↵
↵
void dfs1(int v, int pr) {↵
T.push_back(v);↵
cnt1++;↵
for (auto to: g[v]) {↵
if (to != pr && !us[to]) {↵
dfs1(to, v);↵
}↵
}↵
}↵
↵
int dfs(int v, int pr) {↵
bool p = true;↵
int cnt = 1;↵
for (auto to: g[v]) {↵
if (to != pr && !us[to]) {↵
auto u = dfs(to, v);↵
if (u > cnt1 / 2) {↵
p = false;↵
}↵
cnt += u;↵
}↵
}↵
if (p && (cnt1 — cnt) <= cnt1 / 2) {↵
h = v;↵
}↵
return cnt;↵
}↵
↵
int E = 0;↵
↵
vector<int> ans;↵
vector<vector<int>> mn;↵
vector<int> col;↵
vector<int> sz;↵
vector<int> W;↵
↵
void dfs(int v, int pr, vector<int> s, int an, int o, int mx) {↵
sz[v] = o;↵
col[v] = E;↵
W[v] = W[pr];↵
for (int i = 0; i < 20; ++i) { ↵
mn[v][i] = mn[pr][i];↵
}↵
for (int i = 0; i < 20; ++i) {↵
if ((a[v] >> i) & 1) {↵
if (mn[v][i] != INF) {↵
W[v] = min(W[v], o);↵
}↵
mn[v][i] = min(mn[v][i], o);↵
mx = max(mx, s[i]);↵
s[i] = o;↵
}↵
}↵
an += o — mx;↵
ans[v] = an;↵
for (auto to: g[v]) {↵
if (to != pr && !us[to]) {↵
dfs(to, v, s, an, o + 1, mx);↵
}↵
}↵
}↵
↵
vector<vector<pair<int, int>>> que;↵
vector<int> ANS;↵
↵
void rec(int v) {↵
T.clear();↵
cnt1 = 0;↵
dfs1(v, -1);↵
dfs(v, -1);↵
v = h;↵
us[v] = true;↵
mn[v] = vector<int>(20, INF);↵
int S = E;↵
W[v] = INF;↵
for (auto to: g[v]) {↵
if (!us[to]) {↵
E++;↵
vector<int> s(20, 0);↵
dfs(to, v, s, 0, 1, 0);↵
}↵
}↵
ans[v] = 0;↵
++E;↵
col[v] = E;↵
for (auto x: T) {↵
for (auto [y, id]: que[x]) {↵
if (col[x] != col[y] && col[x] > S && col[y] > S) {↵
ANS[id] = ans[x] + ans[y];↵
if (x == v) {↵
int MN = min(W[y], sz[y] + 1);↵
for (int i = 0; i < 20; ++i) {↵
if ((a[v] >> i) & 1) {↵
MN = min(MN, mn[y][i]);↵
}↵
}↵
ANS[id] += MN;↵
} else if (y == v) {↵
int MN = min(W[x], sz[x] + 1);↵
for (int i = 0; i < 20; ++i) {↵
if ((a[v] >> i) & 1) {↵
MN = min(MN, mn[x][i]);↵
}↵
}↵
ANS[id] += MN;↵
} else {↵
vector<pair<int, int>> upd;↵
for (int i = 0; i < 20; ++i) {↵
if (mn[x][i] != INF) {↵
upd.push_back({mn[x][i], i});↵
}↵
}↵
int e = min(W[y], sz[y] + 1);↵
for (int i = 0; i < 20; ++i) {↵
if ((a[v] >> i) & 1) {↵
e = min(e, mn[y][i]);↵
}↵
}↵
sort(upd.begin(), upd.end());↵
int p = 0;↵
bool flag = true;↵
for (int i = 0; i < upd.size(); ++i) {↵
if (upd[i].first >= W[x]) {↵
ANS[id] += (W[x] — p) * e;↵
flag = false;↵
break;↵
}↵
ANS[id] += (upd[i].first — p) * e;↵
if ((a[v] >> upd[i].second) & 1) {↵
flag = false;↵
break;↵
}↵
e = min(e, mn[y][upd[i].second]);↵
p = upd[i].first;↵
}↵
if (flag) {↵
ANS[id] += (min(W[x], sz[x] + 1) — p) * e;↵
}↵
}↵
}↵
}↵
}↵
for (int i = 0; i < g[v].size(); ++i) {↵
int to = g[v][i];↵
if (!us[to]) {↵
rec(to);↵
}↵
}↵
}↵
↵
↵
void solve() {↵
int n, q;↵
cin >> n >> q;↵
sz.clear();↵
W.clear();↵
W.resize(n);↵
sz.resize(n);↵
ans.clear();↵
ANS.clear();↵
ANS.resize(q, -1);↵
mn.clear();↵
ans.resize(n);↵
mn.resize(n, vector<int>(20));↵
a.clear();↵
us.clear();↵
us.resize(n);↵
a.resize(n);↵
for (int i = 0; i < n; ++i) {↵
cin >> a[i];↵
}↵
g.clear();↵
col.clear();↵
col.resize(n);↵
que.clear();↵
que.resize(n);↵
g.resize(n);↵
for (int i = 0; i < n — 1; ++i) {↵
int u, v;↵
cin >> u >> v;↵
--u;↵
--v;↵
g[u].push_back(v);↵
g[v].push_back(u);↵
}↵
for (int i = 0; i < q; ++i) {↵
int x, y;↵
cin >> x >> y;↵
--x;↵
--y;↵
que[x].push_back({y, i});↵
}↵
rec(0);↵
for (int i = 0; i < q; ++i) {↵
if (ANS[i] == -1) {↵
exit(-1);↵
}↵
cout << ANS[i] << "\n";↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
