[A](https://mirror.codeforces.com/gym/106177/problem/A)↵
↵
Idea:[user:wakanda-forever,2025-11-11]↵
↵
<spoiler summary="solution">↵
↵
For any non-decreasing sequence $(b_1, b_2, \ldots, b_m)$, ↵
$b_1$ $|$ $b_2$ $|$ $b_3$ $|$ $\cdots$ $|$ $b_m$ $\ge$ $b_1$.↵
↵
So, it is always better to consider subsequences of length $1$.↵
Out of these, we can simply choose the smallest element and this is always optimal.↵
↵
Time Complexity: $O(n)$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
```cpp↵
↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
int main(){↵
↵
int t;↵
cin >> t;↵
↵
while(t--){↵
↵
int n;↵
cin >> n;↵
↵
vector<int> a(n);↵
for(int i = 0; i < n; i++) cin >> a[i];↵
↵
cout << *min_element(a.begin(), a.end()) << '\n';↵
↵
}↵
}↵
↵
```↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039A,option1]↵
↵
Good problem: [likes:2039A,option2]↵
↵
Average problem: [likes:2039A,option3]↵
↵
Bad problem: [likes:2039A,option4]↵
↵
Didn't solve: [likes:2039A,option5]↵
</spoiler>↵
↵
↵
[B](https://mirror.codeforces.com/gym/106177/problem/B)↵
↵
Idea:[user:tamzid1,2025-11-11]↵
↵
<spoiler summary="solution">↵
↵
We can observe that $f(i,1)=0$ for $i \ge 1$ and $f(1,i)$ for $i \ge 2$.↵
↵
Thus, "1 n-1" is always a valid answer.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
```C++↵
// By Auchenai01↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ll = long long;↵
using ld = long double;↵
using pii = pair<int, int>;↵
using pll = pair<ll, ll>;↵
using vi = vector<int>;↵
using vvi = vector<vector<int>>;↵
using vl = vector<ll>;↵
using vvl = vector<vector<ll>>;↵
const ll MOD = 998244353;↵
const ll MAXX = 1e16;↵
const int INF = 1e9 + 7;↵
void solve() {↵
int n;↵
cin >> n;↵
cout << 1 << " " << n - 1 << endl;↵
}↵
↵
signed main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
ll t = 1;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
↵
```↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039b,option1]↵
↵
Good problem: [likes:2039b,option2]↵
↵
Average problem: [likes:2039b,option3]↵
↵
Bad problem: [likes:2039b,option4]↵
↵
Didn't solve: [likes:2039b,option5]↵
</spoiler>↵
↵
[C](https://mirror.codeforces.com/gym/106177/problem/C)↵
↵
Idea:[user:tamzid1,2025-11-11], [user:wuhudsm,2025-11-11]↵
↵
<spoiler summary="solution">↵
↵
If $m=1$, the answer is "YES".↵
↵
Otherwise, to make $f(x,i)=1$ for all $2 \le i \le n$, the valuse of $x$ must be at least $\operatorname{lcm}(2,3,\ldots,n)+1$. We can see it will exceed $10^{18}$ when $n$ is larger than $30$.↵
↵
Thus, the solution is: When $m=1$, output "YES". Otherwise, run bruteforce when $n \le 30$ and output "NO" when $n > 30$,↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
↵
↵
~~~~~↵
// By Auchenai01↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ll = long long;↵
using ld = long double;↵
using pii = pair<int, int>;↵
using pll = pair<ll, ll>;↵
using vi = vector<int>;↵
using vvi = vector<vector<int>>;↵
using vl = vector<ll>;↵
using vvl = vector<vector<ll>>;↵
const ll MOD = 998244353;↵
const ll MAXX = 1e16;↵
const int INF = 1e9 + 7;↵
void solve() {↵
int n, m;↵
cin >> n >> m;↵
if (n <= 30) {↵
for (int i = 2; i <= n; i++) {↵
if (m % i != 1) {↵
cout << "NO" << endl;↵
return;↵
}↵
}↵
cout << "YES" << endl;↵
return;↵
}↵
cout << (m == 1 ? "Yes" : "no") << endl;↵
}↵
↵
signed main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
ll t = 1;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039c,option1]↵
↵
Good problem: [likes:2039c,option2]↵
↵
Average problem: [likes:2039c,option3]↵
↵
Bad problem: [likes:2039c,option4]↵
↵
Didn't solve: [likes:2039c,option5]↵
</spoiler>↵
↵
[D](https://mirror.codeforces.com/gym/106177/problem/D)↵
↵
Idea:[user:wakanda-forever,2025-11-11]↵
↵
<spoiler summary="solution">↵
↵
Let's assume $\operatorname{mex}(a_1, a3, \ldots, a{n-1}) = p$ and $\operatorname{mex}(a_2, a4, \ldots, a{n}) = q$. Now the condition becomes $\operatorname{mex}(p, q) = \operatorname{mex}(a_1, a_2, a_3, \ldots, a_n)$.↵
↵
We can see that the inequality $\operatorname{mex}(p, q) \le 2$ holds for any value of $p$ and $q$. So, we can simply check the three possible cases:↵
↵
Case I: $\operatorname{mex}(p, q) = 0$↵
↵
Here, we should have $p > 0$ and $q > 0$, and this implies that there are at least two 0's in the array $a$. Then, we have $\operatorname{mex}(a_1, a_2, a_3, \ldots, a_n) > 0 = \operatorname{mex}(p, q)$.↵
↵
So, the array is not good in this case.↵
↵
Case II: $\operatorname{mex}(p, q) = 1$↵
↵
Here, we should have $p = 0$ and $q \ne 1$, or $p \ne 1$ and $q = 0$. In any case, $\operatorname{mex}(a_1, a_2, a_3, \ldots, a_n) \ne 1 = \operatorname{mex}(p, q)$. ↵
↵
So, the array is not good in this case.↵
↵
Case III: $\operatorname{mex}(p, q) = 2$↵
↵
Here, we should have $p = 0$ and $q = 1$, or $p = 1$ and $q = 0$. For the array to be good, we should also have $\operatorname{mex}(a_1, a_2, a_3, \ldots, a_n) = 2$.↵
↵
↵
↵
Thus, an array is good if it's $\operatorname{mex} = 2$ and $\operatorname{mex}$ of even and odd indexed values are $0$ and $1$.↵
↵
So, any array of length $n$ can be rearranged into a good array if all the following conditions are satisfied:↵
↵
- $\operatorname{mex}$ of array is $2$.↵
↵
- number of 0's in the array $\le \frac{n}{2}$.↵
↵
- number of 1's in the array $\le \frac{n}{2}$.↵
↵
Time Complexity: $O(n)$.↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="code">↵
```cpp↵
// By Auchenai01↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ll = long long;↵
using ld = long double;↵
using pii = pair<int, int>;↵
using pll = pair<ll, ll>;↵
using vi = vector<int>;↵
using vvi = vector<vector<int>>;↵
using vl = vector<ll>;↵
using vvl = vector<vector<ll>>;↵
const ll MOD = 998244353;↵
const ll MAXX = 1e16;↵
const int INF = 1e9 + 7;↵
void solve() {↵
int n;↵
cin >> n;↵
vi a(n);↵
vi cnt(n + 1);↵
for (int i = 0; i < n; i++) {↵
cin >> a[i];↵
cnt[a[i]]++;↵
}↵
if (cnt[0] == 0) {↵
cout << "NO" << endl;↵
return;↵
}↵
if (cnt[1] == 0) {↵
cout << "NO" << endl;↵
return;↵
}↵
if (cnt[2] > 0) {↵
cout << "NO" << endl;↵
return;↵
}↵
if (cnt[0] > n / 2 || cnt[1] > n / 2) {↵
cout << "NO" << endl;↵
} else {↵
cout << "YES" << endl;↵
}↵
}↵
↵
signed main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
ll t = 1;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
↵
↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039d,option1]↵
↵
Good problem: [likes:2039d,option2]↵
↵
Average problem: [likes:2039d,option3]↵
↵
Bad problem: [likes:2039d,option4]↵
↵
Didn't solve: [likes:2039d,option5]↵
</spoiler>↵
↵
[E](https://mirror.codeforces.com/gym/106177/problem/E)↵
↵
Idea:[user:sanju77,2025-11-11]↵
↵
<spoiler summary="solution">↵
↵
Let $pre_i=\max_{1 \le j \le i}(a_j+a_{j+1}+\ldots+a_i)$, and $suf_i=\max_{i \le j \le n}(a_i+a_{i+1}+\ldots+a_j)$.↵
↵
The answer is $\max_{1 \le j \le i \le}(pre_i+suf_j)$. ↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
↵
#include<bits/stdc++.h> ↵
↵
using namespace std; ↵
↵
typedef long double ld;↵
typedef long long ll;↵
#define all(x) x.begin(), x.end()↵
#define int long long↵
#define C(x) ((x) * ((x) - 1) / 2)↵
↵
void solve()↵
{↵
int n;↵
cin >> n;↵
int a[n];↵
for(int i = 0; i < n; i ++)↵
cin >> a[i];↵
↵
ll ans = 0, suf = 0, sm = 0;↵
ll pref[n + 1] = {};↵
pref[0] = 0;↵
for(int i = 0; i < n; i ++)↵
{↵
sm += a[i];↵
sm = max(0ll, sm);↵
ans = max(ans, sm);↵
pref[i + 1] = ans;↵
}↵
ans = pref[n - 1];↵
sm = 0;↵
for(int i = n - 1; i > 0; i--)↵
{↵
sm += a[i];↵
sm = max(0ll, sm);↵
suf = max(suf, sm);↵
ans = max(pref[i - 1] + suf, ans);↵
} ↵
↵
cout << ans << endl;↵
↵
}↵
// if i % 2 == 1, i + 2, else i - 2↵
signed main()↵
{ ↵
ios::sync_with_stdio(false);↵
cin.tie(0), cout.tie(0);↵
↵
int t = 1;↵
cin >> t;↵
while(t--)↵
solve();↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039e,option1]↵
↵
Good problem: [likes:2039e,option2]↵
↵
Average problem: [likes:2039e,option3]↵
↵
Bad problem: [likes:2039e,option4]↵
↵
Didn't solve: [likes:2039e,option5]↵
</spoiler>↵
↵
↵
[F](https://mirror.codeforces.com/gym/106177/problem/F)↵
↵
Idea:[user:wakanda-forever,2025-11-11]↵
↵
↵
<spoiler summary="solution">↵
↵
Observe that $x \oplus (x + 1) = 1$ when $x$ is even. This expression can be used to reduce $f(x)$.↵
↵
$$↵
\mathrm{f(x)} = \begin{cases}↵
x + 2 & \text{if } x \text{ is odd},\↵
x - 2 & \text{if } x \text{ is even}.↵
\end{cases}↵
$$↵
↵
Now, consider an array $b$ of length $m$. Let the number of odd values in the array be $p$. Let's check for the conditions which make the array good.↵
↵
Case I: $p$ is even↵
↵
Now, the total sum is even. So, $f(b_1 + b_2 + \cdots + b_m) = b_1 + b_2 + \cdots + b_m - 2$.↵
↵
For array $b$ to be good, $(#\text{even}) - (#\text{odd}) = 1$.↵
↵
Case II: $p$ is odd↵
↵
Now, the total sum is odd. So, $f(b_1 + b_2 + \cdots + b_m) = b_1 + b_2 + \cdots + b_m + 2$.↵
↵
For array $b$ to be good, $(#\text{even}) - (#\text{odd}) = -1$.↵
↵
We can count subarrays of these two types using map and prefix sums.↵
↵
Time Complexity: $O(n\text{log}n)$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
↵
// By Auchenai01↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ll = long long;↵
using ld = long double;↵
using pii = pair<int, int>;↵
using pll = pair<ll, ll>;↵
using vi = vector<int>;↵
using vvi = vector<vector<int>>;↵
using vl = vector<ll>;↵
using vvl = vector<vector<ll>>;↵
const ll MOD = 998244353;↵
const ll MAXX = 1e16;↵
const int INF = 1e9 + 7;↵
void solve() {↵
int n;↵
cin >> n;↵
vi a(n);↵
for (int i = 0; i < n; i++) {↵
cin >> a[i];↵
}↵
vvi cnt(4, vi(2 * n + 1));↵
cnt[3][n] = 1;↵
int cur = n;↵
ll ans = 0;↵
for (int i = 0; i < n; i++) {↵
cur += ((a[i] % 2) ? 1 : -1);↵
cnt[i % 4][cur]++;↵
if (cur) ans += cnt[(i + 3) % 4][cur-1];↵
if (cur < 2 * n) ans += cnt[(i + 3) % 4][cur+1];↵
}↵
cout << ans << endl;↵
}↵
↵
signed main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
ll t = 1;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039f,option1]↵
↵
Good problem: [likes:2039f,option2]↵
↵
Average problem: [likes:2039f,option3]↵
↵
Bad problem: [likes:2039f,option4]↵
↵
Didn't solve: [likes:2039f,option5]↵
</spoiler>↵
↵
[G](https://mirror.codeforces.com/gym/106049177/problem/G)↵
↵
Idea:[user:gentlecoder29,2025-11-11]↵
↵
↵
<spoiler summary="solution">↵
↵
Several important observations:↵
- If a node $x$ is the last node traversed by a node $i$, ($a_i = x$), then $a_x = x$.↵
↵
- No other node, apart from the root node, can have the root node as the last traversed node, i.e., if $a_i = r$, then $i = r$.↵
↵
- $a_i$ appears later than $i$ in the inorder traversal of the full binary tree.↵
↵
- $a_r$ (where $r$ is the root) should be the last node in the inorder traversal of the full binary tree.↵
↵
This gives us a simple solution -↵
↵
- First check whether $a_{a_i} = a_i$ $\forall$ $i, 1 \leq i \leq n$.↵
↵
- Then check if $a_i = r$ for $i \neq r$.↵
↵
- After doing these checks, a traversal can be constructed as follows-↵
- For a node $x$, map all those nodes $y$ such that $a_y = x$.↵
- Mark a special node $last$ such that $a_r = last$. ↵
- Run a greedy solution over all nodes except the special node and first add those nodes to the traversal which are in the map and then that node itself.↵
- Then finally add the root and the nodes in map of special node and then the special node itself.↵
↵
Also look at the code for more clarification.↵
↵
---↵
↵
BONUS: can you implement the checker?↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
↵
// By Auchenai01↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ll = long long;↵
using ld = long double;↵
using pii = pair<int, int>;↵
using pll = pair<ll, ll>;↵
using vi = vector<int>;↵
using vvi = vector<vector<int>>;↵
using vl = vector<ll>;↵
using vvl = vector<vector<ll>>;↵
const ll MOD = 998244353;↵
const ll MAXX = 1e16;↵
const int INF = 1e9 + 7;↵
class DSU {↵
public:↵
vector<int> parent, size;↵
DSU(int n) {↵
parent.resize(n);↵
size.resize(n, 1);↵
for (int i = 0; i < n; ++i) {↵
parent[i] = i; ↵
}↵
}↵
int find(int x) {↵
if (parent[x] != x) {↵
parent[x] = find(parent[x]); ↵
}↵
return parent[x];↵
}↵
void unite(int a, int b) {↵
a = find(a), b = find(b);↵
if (a != b) {↵
if (size[a] < size[b]) swap(a, b);↵
parent[b] = a;↵
size[a] += size[b];↵
}↵
}↵
};↵
void solve() {↵
int n, r;↵
cin >> n >> r;↵
r--;↵
DSU D(n);↵
vi a(n);↵
for (int i = 0; i < n; i++) {↵
int x;↵
cin >> x;↵
x--;↵
D.unite(x, i);↵
a[i] = x;↵
}↵
for (int i = 0; i < n; i++) {↵
if (a[i] == r && i != r) {↵
cout << -1 << endl;↵
return;↵
}↵
}↵
vi P(n, -1);↵
vvi V(n);↵
int mark = -1;↵
for (int i = 0; i < n; i++) {↵
int y = D.find(i);↵
if (P[y] == -1) {↵
P[y] = a[i];↵
} else if (P[y] != a[i]) {↵
cout << -1 << endl;↵
return;↵
}↵
V[a[i]].push_back(i);↵
if (i == r) {↵
mark = a[i];↵
}↵
}↵
vi ans;↵
for (int i = 0; i < n; i++) {↵
if (i != mark) {↵
for (int v : V[i]) {↵
if (v != i) ans.push_back(v);↵
}↵
if (V[i].size()) ans.push_back(i);↵
}↵
}↵
ans.push_back(r);↵
for (int v : V[mark]) {↵
if (v != mark && v != r) ans.push_back(v);↵
}↵
if (mark != r && V[mark].size()) ans.push_back(mark);↵
assert(ans.size() == n);↵
for (int i = 0; i < n; i++) {↵
cout << ans[i] + 1 << " ";↵
}↵
cout << endl;↵
}↵
↵
signed main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
ll t = 1;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039g,option1]↵
↵
Good problem: [likes:2039g,option2]↵
↵
Average problem: [likes:2039g,option3]↵
↵
Bad problem: [likes:2039g,option4]↵
↵
Didn't solve: [likes:2039g,option5]↵
</spoiler>↵
↵
[H](https://mirror.codeforces.com/gym/106177/problem/H)↵
↵
Idea:[user:kaosar_the_Joyboy,2025-11-11],[user:wuhudsm,2025-01-23]↵
↵
↵
<spoiler summary="solution">↵
↵
Let's find the minimum value first. ↵
↵
We can see there exists a sequence of operations where the last operation is the G-operation and obtains the minimum value. Since $\operatorname{lcm}(x,y) \ge \operatorname{gcd}(x,y)$, all sequences where the last operation is an L-operation have a value greater than or equal to the value of sequences where the last operation is a G-operation.↵
↵
When we fix using $s_n='G'$, we only care about the gcd value of the current value and $a_n$. Thus, we have $dp_{i,j,k= 0/1}$ ~--- the number if schemes in the first $i$ operations, where the gcd value of the current value and $a_n$ is $j$ and the last operation is $k$. ↵
↵
In this way, we can obtain the number of valid operation sequences when $s_n='G'$. Now lets consier a operation sequences like $s=" \ldots GLL \ldots L"$. We can see $s_j=s_{j+1}=\ldots=s_{n}='L'$ is valid only if $\operatorname{gcd}(a_j,a_{j+1},\ldots,a_n)=a_n$. For such $j$, we can update the answer with the original dp value.↵
↵
Then we sill need to find the maximum index $mx$ such that $\operatorname{gcd}(a_j,a_{j+1},\ldots,a_n) \neq a_n$. We can see the $mx$-th operation must be a $G$-operation. We need to do the above dp again, but this time, we only care about the gcd value of the current value and $a_{mx}$.↵
↵
Time Complexity: $O(n \cdot \operatorname{divisors}(A) \cdot \log(A))$.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include <map>↵
#include <set>↵
#include <cmath>↵
#include <ctime>↵
#include <queue>↵
#include <stack>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <vector>↵
#include <cstring>↵
#include <algorithm>↵
#include <iostream>↵
#include <bitset>↵
#include <unordered_map>↵
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
using namespace std;↵
typedef double db;↵
typedef long long ll;↵
typedef unsigned long long ull;↵
const int N=1000010;↵
const int LOGN=28;↵
const ll TMD=998244353;↵
const ll INF=2147483647;↵
int T;↵
ll n,x;↵
ll a[N];↵
map<ll,ll> dp[N][2];↵
↵
/*↵
* stuff you should look for↵
* [Before Submission]↵
* array bounds, initialization, int overflow, special cases (like n=1), typo↵
* [Still WA]↵
* check typo carefully↵
* casework mistake↵
* special bug↵
* stress test↵
*/↵
↵
//-------------------------------------------------↵
↵
vector<ll> divs[N];↵
↵
void init_divs()↵
{↵
for(int i=1;i<N;i++)↵
for(int j=1;j*i<N;j++)↵
divs[j*i].push_back(i);↵
}↵
↵
//-------------------------------------------------↵
↵
ll gcd(ll a,ll b)↵
{↵
return b?gcd(b,a%b):a;↵
}↵
↵
ll lcm(ll a,ll b)↵
{↵
return a*b/gcd(a,b);↵
}↵
↵
void init()↵
{↵
cin>>n>>x;↵
for(int i=1;i<=n;i++)↵
cin>>a[i];↵
}↵
↵
void DP(ll k)↵
{↵
//↵
//printf("DP\n");↵
//↵
for(int i=1;i<=n;i++)↵
for(int j=0;j<=1;j++)↵
dp[i][j].clear();↵
queue<tuple<ll,ll,ll> > Q;↵
dp[1][0][gcd(k,gcd(x,a[1]))]=1;↵
dp[1][1][gcd(k,lcm(x,a[1]))]=1;↵
Q.push({1,0,gcd(k,gcd(x,a[1]))});↵
Q.push({1,1,gcd(k,lcm(x,a[1]))});↵
while(!Q.empty())↵
{↵
tuple<ll,ll,ll> t=Q.front();↵
ll i=get<0>(t),ty=get<1>(t),val=get<2>(t);↵
Q.pop();↵
//↵
// printf("i=%lld ty=%lld val=%lld dp=%lld\n",i,ty,val,dp[i][ty][val]);↵
//↵
if(i==n) continue;↵
if(ty)↵
{↵
ll vg=gcd(k,gcd(val,a[i+1])),vl=gcd(k,lcm(val,a[i+1]));↵
if(!dp[i+1][0][vg]) Q.push({i+1,0,vg});↵
dp[i+1][0][vg]+=dp[i][1][val],dp[i+1][0][vg]%=TMD;↵
if(!dp[i+1][1][vl]) Q.push({i+1,1,vl});↵
dp[i+1][1][vl]+=dp[i][1][val],dp[i+1][1][vl]%=TMD;↵
}↵
else↵
{↵
ll vl=gcd(k,lcm(val,a[i+1]));↵
if(!dp[i+1][1][vl]) Q.push({i+1,1,vl});↵
dp[i+1][1][vl]+=dp[i][0][val],dp[i+1][1][vl]%=TMD;↵
}↵
}↵
}↵
↵
void solve()↵
{↵
//↵
//printf("solve\n");↵
//↵
ll mn=x,ans=0;↵
for(int i=1;i<=n;i++)↵
{↵
if((i&1)==(n&1)) mn=gcd(mn,a[i]);↵
else mn=lcm(mn,a[i]);↵
}↵
DP(a[n]);↵
if(mn!=a[n])↵
{↵
cout<<mn<<" "<<dp[n][0][mn]<<"\n";↵
return ;↵
}↵
//↵
//↵
//printf("solve2 mn=%lld\n",mn);↵
//↵
ans=dp[n][0][mn];↵
for(int i=n-1;i;i--)↵
{↵
if(a[n]%a[i])↵
{↵
//↵
//printf("before i=%d ans=%lld\n",i,ans);↵
//↵
DP(a[i]);↵
for(auto &j:dp[i][0])↵
if(!(a[n]%j.first)) ans+=j.second,ans%=TMD;↵
//↵
//printf("after i=%d ans=%lld\n",i,ans);↵
//↵
break;↵
}↵
else↵
{↵
for(auto &j:dp[i][0])↵
ans+=j.second,ans%=TMD;↵
}↵
}↵
ans++; //LLL...L↵
ans%=TMD;↵
a[0]=x;↵
for(int i=0;i<=n;i++)↵
{↵
if(a[n]%a[i])↵
{↵
ans+=TMD-1;↵
ans%=TMD;↵
break;↵
}↵
}↵
//↵
cout<<mn<<" "<<ans<<"\n";↵
}↵
↵
//-------------------------------------------------------↵
↵
void gen_data()↵
{↵
srand(time(NULL));↵
}↵
↵
int bruteforce()↵
{↵
return 0;↵
}↵
↵
//-------------------------------------------------------↵
↵
int main()↵
{↵
fastio;↵
↵
init_divs();↵
cin>>T;↵
while(T--)↵
{↵
init();↵
solve();↵
↵
/*↵
↵
//Stress Test↵
↵
gen_data();↵
auto ans1=solve(),ans2=bruteforce();↵
if(ans1==ans2) printf("OK!\n");↵
else↵
{↵
//Output Data↵
}↵
↵
*/↵
}↵
↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039h,option1]↵
↵
Good problem: [likes:2039h,option2]↵
↵
Average problem: [likes:2039h,option3]↵
↵
Bad problem: [likes:2039h,option4]↵
↵
Didn't solve: [likes:2039h,option5]↵
</spoiler>↵
↵
↵
↵
↵
Idea:[user:wakanda-forever,2025-11-11]↵
↵
<spoiler summary="solution">↵
↵
For any non-decreasing sequence $(b_1, b_2, \ldots, b_m)$, ↵
$b_1$ $|$ $b_2$ $|$ $b_3$ $|$ $\cdots$ $|$ $b_m$ $\ge$ $b_1$.↵
↵
So, it is always better to consider subsequences of length $1$.↵
Out of these, we can simply choose the smallest element and this is always optimal.↵
↵
Time Complexity: $O(n)$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
```cpp↵
↵
#include<bits/stdc++.h>↵
using namespace std;↵
↵
int main(){↵
↵
int t;↵
cin >> t;↵
↵
while(t--){↵
↵
int n;↵
cin >> n;↵
↵
vector<int> a(n);↵
for(int i = 0; i < n; i++) cin >> a[i];↵
↵
cout << *min_element(a.begin(), a.end()) << '\n';↵
↵
}↵
}↵
↵
```↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039A,option1]↵
↵
Good problem: [likes:2039A,option2]↵
↵
Average problem: [likes:2039A,option3]↵
↵
Bad problem: [likes:2039A,option4]↵
↵
Didn't solve: [likes:2039A,option5]↵
</spoiler>↵
↵
↵
[B](https://mirror.codeforces.com/gym/106177/problem/B)↵
↵
Idea:[user:tamzid1,2025-11-11]↵
↵
<spoiler summary="solution">↵
↵
We can observe that $f(i,1)=0$ for $i \ge 1$ and $f(1,i)$ for $i \ge 2$.↵
↵
Thus, "1 n-1" is always a valid answer.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code(C++)">↵
↵
```C++↵
// By Auchenai01↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ll = long long;↵
using ld = long double;↵
using pii = pair<int, int>;↵
using pll = pair<ll, ll>;↵
using vi = vector<int>;↵
using vvi = vector<vector<int>>;↵
using vl = vector<ll>;↵
using vvl = vector<vector<ll>>;↵
const ll MOD = 998244353;↵
const ll MAXX = 1e16;↵
const int INF = 1e9 + 7;↵
void solve() {↵
int n;↵
cin >> n;↵
cout << 1 << " " << n - 1 << endl;↵
}↵
↵
signed main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
ll t = 1;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
↵
```↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039b,option1]↵
↵
Good problem: [likes:2039b,option2]↵
↵
Average problem: [likes:2039b,option3]↵
↵
Bad problem: [likes:2039b,option4]↵
↵
Didn't solve: [likes:2039b,option5]↵
</spoiler>↵
↵
[C](https://mirror.codeforces.com/gym/106177/problem/C)↵
↵
Idea:[user:tamzid1,2025-11-11], [user:wuhudsm,2025-11-11]↵
↵
<spoiler summary="solution">↵
↵
If $m=1$, the answer is "YES".↵
↵
Otherwise, to make $f(x,i)=1$ for all $2 \le i \le n$, the valuse of $x$ must be at least $\operatorname{lcm}(2,3,\ldots,n)+1$. We can see it will exceed $10^{18}$ when $n$ is larger than $30$.↵
↵
Thus, the solution is: When $m=1$, output "YES". Otherwise, run bruteforce when $n \le 30$ and output "NO" when $n > 30$,↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
↵
↵
~~~~~↵
// By Auchenai01↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ll = long long;↵
using ld = long double;↵
using pii = pair<int, int>;↵
using pll = pair<ll, ll>;↵
using vi = vector<int>;↵
using vvi = vector<vector<int>>;↵
using vl = vector<ll>;↵
using vvl = vector<vector<ll>>;↵
const ll MOD = 998244353;↵
const ll MAXX = 1e16;↵
const int INF = 1e9 + 7;↵
void solve() {↵
int n, m;↵
cin >> n >> m;↵
if (n <= 30) {↵
for (int i = 2; i <= n; i++) {↵
if (m % i != 1) {↵
cout << "NO" << endl;↵
return;↵
}↵
}↵
cout << "YES" << endl;↵
return;↵
}↵
cout << (m == 1 ? "Yes" : "no") << endl;↵
}↵
↵
signed main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
ll t = 1;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039c,option1]↵
↵
Good problem: [likes:2039c,option2]↵
↵
Average problem: [likes:2039c,option3]↵
↵
Bad problem: [likes:2039c,option4]↵
↵
Didn't solve: [likes:2039c,option5]↵
</spoiler>↵
↵
[D](https://mirror.codeforces.com/gym/106177/problem/D)↵
↵
Idea:[user:wakanda-forever,2025-11-11]↵
↵
<spoiler summary="solution">↵
↵
Let's assume $\operatorname{mex}(a_1, a3, \ldots, a{n-1}) = p$ and $\operatorname{mex}(a_2, a4, \ldots, a{n}) = q$. Now the condition becomes $\operatorname{mex}(p, q) = \operatorname{mex}(a_1, a_2, a_3, \ldots, a_n)$.↵
↵
We can see that the inequality $\operatorname{mex}(p, q) \le 2$ holds for any value of $p$ and $q$. So, we can simply check the three possible cases:↵
↵
Case I: $\operatorname{mex}(p, q) = 0$↵
↵
Here, we should have $p > 0$ and $q > 0$, and this implies that there are at least two 0's in the array $a$. Then, we have $\operatorname{mex}(a_1, a_2, a_3, \ldots, a_n) > 0 = \operatorname{mex}(p, q)$.↵
↵
So, the array is not good in this case.↵
↵
Case II: $\operatorname{mex}(p, q) = 1$↵
↵
Here, we should have $p = 0$ and $q \ne 1$, or $p \ne 1$ and $q = 0$. In any case, $\operatorname{mex}(a_1, a_2, a_3, \ldots, a_n) \ne 1 = \operatorname{mex}(p, q)$. ↵
↵
So, the array is not good in this case.↵
↵
Case III: $\operatorname{mex}(p, q) = 2$↵
↵
Here, we should have $p = 0$ and $q = 1$, or $p = 1$ and $q = 0$. For the array to be good, we should also have $\operatorname{mex}(a_1, a_2, a_3, \ldots, a_n) = 2$.↵
↵
↵
↵
Thus, an array is good if it's $\operatorname{mex} = 2$ and $\operatorname{mex}$ of even and odd indexed values are $0$ and $1$.↵
↵
So, any array of length $n$ can be rearranged into a good array if all the following conditions are satisfied:↵
↵
- $\operatorname{mex}$ of array is $2$.↵
↵
- number of 0's in the array $\le \frac{n}{2}$.↵
↵
- number of 1's in the array $\le \frac{n}{2}$.↵
↵
Time Complexity: $O(n)$.↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="code">↵
```cpp↵
// By Auchenai01↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ll = long long;↵
using ld = long double;↵
using pii = pair<int, int>;↵
using pll = pair<ll, ll>;↵
using vi = vector<int>;↵
using vvi = vector<vector<int>>;↵
using vl = vector<ll>;↵
using vvl = vector<vector<ll>>;↵
const ll MOD = 998244353;↵
const ll MAXX = 1e16;↵
const int INF = 1e9 + 7;↵
void solve() {↵
int n;↵
cin >> n;↵
vi a(n);↵
vi cnt(n + 1);↵
for (int i = 0; i < n; i++) {↵
cin >> a[i];↵
cnt[a[i]]++;↵
}↵
if (cnt[0] == 0) {↵
cout << "NO" << endl;↵
return;↵
}↵
if (cnt[1] == 0) {↵
cout << "NO" << endl;↵
return;↵
}↵
if (cnt[2] > 0) {↵
cout << "NO" << endl;↵
return;↵
}↵
if (cnt[0] > n / 2 || cnt[1] > n / 2) {↵
cout << "NO" << endl;↵
} else {↵
cout << "YES" << endl;↵
}↵
}↵
↵
signed main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
ll t = 1;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
↵
↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039d,option1]↵
↵
Good problem: [likes:2039d,option2]↵
↵
Average problem: [likes:2039d,option3]↵
↵
Bad problem: [likes:2039d,option4]↵
↵
Didn't solve: [likes:2039d,option5]↵
</spoiler>↵
↵
[E](https://mirror.codeforces.com/gym/106177/problem/E)↵
↵
Idea:[user:sanju77,2025-11-11]↵
↵
<spoiler summary="solution">↵
↵
Let $pre_i=\max_{1 \le j \le i}(a_j+a_{j+1}+\ldots+a_i)$, and $suf_i=\max_{i \le j \le n}(a_i+a_{i+1}+\ldots+a_j)$.↵
↵
The answer is $\max_{1 \le j \le i \le}(pre_i+suf_j)$. ↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
↵
#include<bits/stdc++.h> ↵
↵
using namespace std; ↵
↵
typedef long double ld;↵
typedef long long ll;↵
#define all(x) x.begin(), x.end()↵
#define int long long↵
#define C(x) ((x) * ((x) - 1) / 2)↵
↵
void solve()↵
{↵
int n;↵
cin >> n;↵
int a[n];↵
for(int i = 0; i < n; i ++)↵
cin >> a[i];↵
↵
ll ans = 0, suf = 0, sm = 0;↵
ll pref[n + 1] = {};↵
pref[0] = 0;↵
for(int i = 0; i < n; i ++)↵
{↵
sm += a[i];↵
sm = max(0ll, sm);↵
ans = max(ans, sm);↵
pref[i + 1] = ans;↵
}↵
ans = pref[n - 1];↵
sm = 0;↵
for(int i = n - 1; i > 0; i--)↵
{↵
sm += a[i];↵
sm = max(0ll, sm);↵
suf = max(suf, sm);↵
ans = max(pref[i - 1] + suf, ans);↵
} ↵
↵
cout << ans << endl;↵
↵
}↵
// if i % 2 == 1, i + 2, else i - 2↵
signed main()↵
{ ↵
ios::sync_with_stdio(false);↵
cin.tie(0), cout.tie(0);↵
↵
int t = 1;↵
cin >> t;↵
while(t--)↵
solve();↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039e,option1]↵
↵
Good problem: [likes:2039e,option2]↵
↵
Average problem: [likes:2039e,option3]↵
↵
Bad problem: [likes:2039e,option4]↵
↵
Didn't solve: [likes:2039e,option5]↵
</spoiler>↵
↵
↵
[F](https://mirror.codeforces.com/gym/106177/problem/F)↵
↵
Idea:[user:wakanda-forever,2025-11-11]↵
↵
↵
<spoiler summary="solution">↵
↵
Observe that $x \oplus (x + 1) = 1$ when $x$ is even. This expression can be used to reduce $f(x)$.↵
↵
$$↵
\mathrm{f(x)} = \begin{cases}↵
x + 2 & \text{if } x \text{ is odd},\↵
x - 2 & \text{if } x \text{ is even}.↵
\end{cases}↵
$$↵
↵
Now, consider an array $b$ of length $m$. Let the number of odd values in the array be $p$. Let's check for the conditions which make the array good.↵
↵
Case I: $p$ is even↵
↵
Now, the total sum is even. So, $f(b_1 + b_2 + \cdots + b_m) = b_1 + b_2 + \cdots + b_m - 2$.↵
↵
For array $b$ to be good, $(#\text{even}) - (#\text{odd}) = 1$.↵
↵
Case II: $p$ is odd↵
↵
Now, the total sum is odd. So, $f(b_1 + b_2 + \cdots + b_m) = b_1 + b_2 + \cdots + b_m + 2$.↵
↵
For array $b$ to be good, $(#\text{even}) - (#\text{odd}) = -1$.↵
↵
We can count subarrays of these two types using map and prefix sums.↵
↵
Time Complexity: $O(n\text{log}n)$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
↵
// By Auchenai01↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ll = long long;↵
using ld = long double;↵
using pii = pair<int, int>;↵
using pll = pair<ll, ll>;↵
using vi = vector<int>;↵
using vvi = vector<vector<int>>;↵
using vl = vector<ll>;↵
using vvl = vector<vector<ll>>;↵
const ll MOD = 998244353;↵
const ll MAXX = 1e16;↵
const int INF = 1e9 + 7;↵
void solve() {↵
int n;↵
cin >> n;↵
vi a(n);↵
for (int i = 0; i < n; i++) {↵
cin >> a[i];↵
}↵
vvi cnt(4, vi(2 * n + 1));↵
cnt[3][n] = 1;↵
int cur = n;↵
ll ans = 0;↵
for (int i = 0; i < n; i++) {↵
cur += ((a[i] % 2) ? 1 : -1);↵
cnt[i % 4][cur]++;↵
if (cur) ans += cnt[(i + 3) % 4][cur-1];↵
if (cur < 2 * n) ans += cnt[(i + 3) % 4][cur+1];↵
}↵
cout << ans << endl;↵
}↵
↵
signed main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
ll t = 1;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039f,option1]↵
↵
Good problem: [likes:2039f,option2]↵
↵
Average problem: [likes:2039f,option3]↵
↵
Bad problem: [likes:2039f,option4]↵
↵
Didn't solve: [likes:2039f,option5]↵
</spoiler>↵
↵
[G](https://mirror.codeforces.com/gym/106
↵
Idea:[user:gentlecoder29,2025-11-11]↵
↵
↵
<spoiler summary="solution">↵
↵
Several important observations:↵
- If a node $x$ is the last node traversed by a node $i$, ($a_i = x$), then $a_x = x$.↵
↵
- No other node, apart from the root node, can have the root node as the last traversed node, i.e., if $a_i = r$, then $i = r$.↵
↵
- $a_i$ appears later than $i$ in the inorder traversal of the full binary tree.↵
↵
- $a_r$ (where $r$ is the root) should be the last node in the inorder traversal of the full binary tree.↵
↵
This gives us a simple solution -↵
↵
- First check whether $a_{a_i} = a_i$ $\forall$ $i, 1 \leq i \leq n$.↵
↵
- Then check if $a_i = r$ for $i \neq r$.↵
↵
- After doing these checks, a traversal can be constructed as follows-↵
- For a node $x$, map all those nodes $y$ such that $a_y = x$.↵
- Mark a special node $last$ such that $a_r = last$. ↵
- Run a greedy solution over all nodes except the special node and first add those nodes to the traversal which are in the map and then that node itself.↵
- Then finally add the root and the nodes in map of special node and then the special node itself.↵
↵
Also look at the code for more clarification.↵
↵
---↵
↵
BONUS: can you implement the checker?↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
↵
// By Auchenai01↵
#include <bits/stdc++.h>↵
using namespace std;↵
using ll = long long;↵
using ld = long double;↵
using pii = pair<int, int>;↵
using pll = pair<ll, ll>;↵
using vi = vector<int>;↵
using vvi = vector<vector<int>>;↵
using vl = vector<ll>;↵
using vvl = vector<vector<ll>>;↵
const ll MOD = 998244353;↵
const ll MAXX = 1e16;↵
const int INF = 1e9 + 7;↵
class DSU {↵
public:↵
vector<int> parent, size;↵
DSU(int n) {↵
parent.resize(n);↵
size.resize(n, 1);↵
for (int i = 0; i < n; ++i) {↵
parent[i] = i; ↵
}↵
}↵
int find(int x) {↵
if (parent[x] != x) {↵
parent[x] = find(parent[x]); ↵
}↵
return parent[x];↵
}↵
void unite(int a, int b) {↵
a = find(a), b = find(b);↵
if (a != b) {↵
if (size[a] < size[b]) swap(a, b);↵
parent[b] = a;↵
size[a] += size[b];↵
}↵
}↵
};↵
void solve() {↵
int n, r;↵
cin >> n >> r;↵
r--;↵
DSU D(n);↵
vi a(n);↵
for (int i = 0; i < n; i++) {↵
int x;↵
cin >> x;↵
x--;↵
D.unite(x, i);↵
a[i] = x;↵
}↵
for (int i = 0; i < n; i++) {↵
if (a[i] == r && i != r) {↵
cout << -1 << endl;↵
return;↵
}↵
}↵
vi P(n, -1);↵
vvi V(n);↵
int mark = -1;↵
for (int i = 0; i < n; i++) {↵
int y = D.find(i);↵
if (P[y] == -1) {↵
P[y] = a[i];↵
} else if (P[y] != a[i]) {↵
cout << -1 << endl;↵
return;↵
}↵
V[a[i]].push_back(i);↵
if (i == r) {↵
mark = a[i];↵
}↵
}↵
vi ans;↵
for (int i = 0; i < n; i++) {↵
if (i != mark) {↵
for (int v : V[i]) {↵
if (v != i) ans.push_back(v);↵
}↵
if (V[i].size()) ans.push_back(i);↵
}↵
}↵
ans.push_back(r);↵
for (int v : V[mark]) {↵
if (v != mark && v != r) ans.push_back(v);↵
}↵
if (mark != r && V[mark].size()) ans.push_back(mark);↵
assert(ans.size() == n);↵
for (int i = 0; i < n; i++) {↵
cout << ans[i] + 1 << " ";↵
}↵
cout << endl;↵
}↵
↵
signed main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
ll t = 1;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039g,option1]↵
↵
Good problem: [likes:2039g,option2]↵
↵
Average problem: [likes:2039g,option3]↵
↵
Bad problem: [likes:2039g,option4]↵
↵
Didn't solve: [likes:2039g,option5]↵
</spoiler>↵
↵
[H](https://mirror.codeforces.com/gym/106177/problem/H)↵
↵
Idea:[user:kaosar_the_Joyboy,2025-11-11],[user:wuhudsm,2025-01-23]↵
↵
↵
<spoiler summary="solution">↵
↵
Let's find the minimum value first. ↵
↵
We can see there exists a sequence of operations where the last operation is the G-operation and obtains the minimum value. Since $\operatorname{lcm}(x,y) \ge \operatorname{gcd}(x,y)$, all sequences where the last operation is an L-operation have a value greater than or equal to the value of sequences where the last operation is a G-operation.↵
↵
When we fix using $s_n='G'$, we only care about the gcd value of the current value and $a_n$. Thus, we have $dp_{i,j,k= 0/1}$ ~--- the number if schemes in the first $i$ operations, where the gcd value of the current value and $a_n$ is $j$ and the last operation is $k$. ↵
↵
In this way, we can obtain the number of valid operation sequences when $s_n='G'$. Now lets consier a operation sequences like $s=" \ldots GLL \ldots L"$. We can see $s_j=s_{j+1}=\ldots=s_{n}='L'$ is valid only if $\operatorname{gcd}(a_j,a_{j+1},\ldots,a_n)=a_n$. For such $j$, we can update the answer with the original dp value.↵
↵
Then we sill need to find the maximum index $mx$ such that $\operatorname{gcd}(a_j,a_{j+1},\ldots,a_n) \neq a_n$. We can see the $mx$-th operation must be a $G$-operation. We need to do the above dp again, but this time, we only care about the gcd value of the current value and $a_{mx}$.↵
↵
Time Complexity: $O(n \cdot \operatorname{divisors}(A) \cdot \log(A))$.↵
↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include <map>↵
#include <set>↵
#include <cmath>↵
#include <ctime>↵
#include <queue>↵
#include <stack>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <vector>↵
#include <cstring>↵
#include <algorithm>↵
#include <iostream>↵
#include <bitset>↵
#include <unordered_map>↵
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);↵
using namespace std;↵
typedef double db;↵
typedef long long ll;↵
typedef unsigned long long ull;↵
const int N=1000010;↵
const int LOGN=28;↵
const ll TMD=998244353;↵
const ll INF=2147483647;↵
int T;↵
ll n,x;↵
ll a[N];↵
map<ll,ll> dp[N][2];↵
↵
/*↵
* stuff you should look for↵
* [Before Submission]↵
* array bounds, initialization, int overflow, special cases (like n=1), typo↵
* [Still WA]↵
* check typo carefully↵
* casework mistake↵
* special bug↵
* stress test↵
*/↵
↵
//-------------------------------------------------↵
↵
vector<ll> divs[N];↵
↵
void init_divs()↵
{↵
for(int i=1;i<N;i++)↵
for(int j=1;j*i<N;j++)↵
divs[j*i].push_back(i);↵
}↵
↵
//-------------------------------------------------↵
↵
ll gcd(ll a,ll b)↵
{↵
return b?gcd(b,a%b):a;↵
}↵
↵
ll lcm(ll a,ll b)↵
{↵
return a*b/gcd(a,b);↵
}↵
↵
void init()↵
{↵
cin>>n>>x;↵
for(int i=1;i<=n;i++)↵
cin>>a[i];↵
}↵
↵
void DP(ll k)↵
{↵
//↵
//printf("DP\n");↵
//↵
for(int i=1;i<=n;i++)↵
for(int j=0;j<=1;j++)↵
dp[i][j].clear();↵
queue<tuple<ll,ll,ll> > Q;↵
dp[1][0][gcd(k,gcd(x,a[1]))]=1;↵
dp[1][1][gcd(k,lcm(x,a[1]))]=1;↵
Q.push({1,0,gcd(k,gcd(x,a[1]))});↵
Q.push({1,1,gcd(k,lcm(x,a[1]))});↵
while(!Q.empty())↵
{↵
tuple<ll,ll,ll> t=Q.front();↵
ll i=get<0>(t),ty=get<1>(t),val=get<2>(t);↵
Q.pop();↵
//↵
// printf("i=%lld ty=%lld val=%lld dp=%lld\n",i,ty,val,dp[i][ty][val]);↵
//↵
if(i==n) continue;↵
if(ty)↵
{↵
ll vg=gcd(k,gcd(val,a[i+1])),vl=gcd(k,lcm(val,a[i+1]));↵
if(!dp[i+1][0][vg]) Q.push({i+1,0,vg});↵
dp[i+1][0][vg]+=dp[i][1][val],dp[i+1][0][vg]%=TMD;↵
if(!dp[i+1][1][vl]) Q.push({i+1,1,vl});↵
dp[i+1][1][vl]+=dp[i][1][val],dp[i+1][1][vl]%=TMD;↵
}↵
else↵
{↵
ll vl=gcd(k,lcm(val,a[i+1]));↵
if(!dp[i+1][1][vl]) Q.push({i+1,1,vl});↵
dp[i+1][1][vl]+=dp[i][0][val],dp[i+1][1][vl]%=TMD;↵
}↵
}↵
}↵
↵
void solve()↵
{↵
//↵
//printf("solve\n");↵
//↵
ll mn=x,ans=0;↵
for(int i=1;i<=n;i++)↵
{↵
if((i&1)==(n&1)) mn=gcd(mn,a[i]);↵
else mn=lcm(mn,a[i]);↵
}↵
DP(a[n]);↵
if(mn!=a[n])↵
{↵
cout<<mn<<" "<<dp[n][0][mn]<<"\n";↵
return ;↵
}↵
//↵
//↵
//printf("solve2 mn=%lld\n",mn);↵
//↵
ans=dp[n][0][mn];↵
for(int i=n-1;i;i--)↵
{↵
if(a[n]%a[i])↵
{↵
//↵
//printf("before i=%d ans=%lld\n",i,ans);↵
//↵
DP(a[i]);↵
for(auto &j:dp[i][0])↵
if(!(a[n]%j.first)) ans+=j.second,ans%=TMD;↵
//↵
//printf("after i=%d ans=%lld\n",i,ans);↵
//↵
break;↵
}↵
else↵
{↵
for(auto &j:dp[i][0])↵
ans+=j.second,ans%=TMD;↵
}↵
}↵
ans++; //LLL...L↵
ans%=TMD;↵
a[0]=x;↵
for(int i=0;i<=n;i++)↵
{↵
if(a[n]%a[i])↵
{↵
ans+=TMD-1;↵
ans%=TMD;↵
break;↵
}↵
}↵
//↵
cout<<mn<<" "<<ans<<"\n";↵
}↵
↵
//-------------------------------------------------------↵
↵
void gen_data()↵
{↵
srand(time(NULL));↵
}↵
↵
int bruteforce()↵
{↵
return 0;↵
}↵
↵
//-------------------------------------------------------↵
↵
int main()↵
{↵
fastio;↵
↵
init_divs();↵
cin>>T;↵
while(T--)↵
{↵
init();↵
solve();↵
↵
/*↵
↵
//Stress Test↵
↵
gen_data();↵
auto ans1=solve(),ans2=bruteforce();↵
if(ans1==ans2) printf("OK!\n");↵
else↵
{↵
//Output Data↵
}↵
↵
*/↵
}↵
↵
return 0;↵
}↵
↵
~~~~~↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the Problem">↵
Amazing problem: [likes:2039h,option1]↵
↵
Good problem: [likes:2039h,option2]↵
↵
Average problem: [likes:2039h,option3]↵
↵
Bad problem: [likes:2039h,option4]↵
↵
Didn't solve: [likes:2039h,option5]↵
</spoiler>↵
↵
↵
↵
