Joey is low on money. His friend Chandler wants to lend Joey some money, but can't give him directly, as Joey is too proud of himself to accept it. So, in order to trick him, Chandler asks Joey to play a game
In this game, Chandler gives Joey an array \(a_1, a_2, \dots, a_n\) (\(n \geq 2\)) of positive integers (\(a_i \ge 1\))
Joey can perform the following operation on the array any number of times:
Take two indices \(i\) and \(j\)\((1 \le i < j \le n)\)
Choose two integers \(x\) and \(y\) (\(x, y \ge 1\)) such that \(x \cdot y = a_i \cdot a_j\)
Replace \(a_i\) by \(x\) and \(a_j\) by \(y\)
In the end, Joey will get the money equal to the sum of elements of the final array
Find the maximum amount of money \(\mathrm{ans}\) Joey can get but print\(2022 \cdot \mathrm{ans}\). Why multiplied by \(2022\)? Because we are never gonna see it again!
It is guaranteed that the product of all the elements of the array \(a\) doesn't exceed \(10^{12}\)
Input
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \leq t \leq 4000\)). Description of the test cases follows
The first line of each test case contains a single integer \(n\) (\(2 \leq n \leq 50\)) — the length of the array \(a\)
The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq 10^6\)) — the array itself
It's guaranteed that the product of all \(a_i\) doesn't exceed \(10^{12}\) (i. e. \(a_1 \cdot a_2 \cdot \ldots \cdot a_n \le 10^{12}\))
Output
For each test case, print the maximum money Joey can get multiplied by\(2022\)
Example
input
1 2 3 4 5 6 7
3 3 2 3 2 2 1 3 3 1000000 1000000 1
output
1 2 3
28308 8088 2022000000004044
Note
In the first test case, Joey can do the following:
He chooses \(i = 1\) and \(j = 2\) (so he has \(a[i] \cdot a[j] = 6\)), chooses \(x = 6\) and \(y = 1\) and makes \(a[i] = 6\) and \(a[j] = 1\).
Demodogs from the Upside-down have attacked Hawkins again. El wants to reach Mike and also kill as many Demodogs in the way as possible
Hawkins can be represented as an \(n \times n\) grid. The number of Demodogs in a cell at the \(i\)-th row and the \(j\)-th column is \(i \cdot j\). El is at position \((1, 1)\) of the grid, and she has to reach \((n, n)\) where she can find Mike
The only directions she can move are the right (from \((i, j)\) to \((i, j + 1)\)) and the down (from \((i, j)\) to \((i + 1, j)\)). She can't go out of the grid, as there are doors to the Upside-down at the boundaries
Calculate the maximum possible number of Demodogs \(\mathrm{ans}\) she can kill on the way, considering that she kills all Demodogs in cells she visits (including starting and finishing cells)
Print \(2022 \cdot \mathrm{ans}\) modulo \(10^9 + 7\). Modulo \(10^9 + 7\) because the result can be too large and multiplied by \(2022\) because we are never gonna see it again!
(Note, you firstly multiply by \(2022\) and only after that take the remainder.)
Input
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \leq t \leq 10^4\)). Description of the test cases follows
The first line of each test case contains one integer \(n\) (\(2 \leq n \leq 10^9\)) — the size of the grid
Output
For each test case, print a single integer — the maximum number of Demodogs that can be killed multiplied by \(2022\), modulo \(10^9 + 7\)
Example
input
1 2 3 4 5
4 2 3 50 1000000000
output
1 2 3 4
14154 44484 171010650 999589541
Note
In the first test case, for any path chosen by her the number of Demodogs to be killed would be \(7\), so the answer would be \(2022 \cdot 7 = 14154\)
You are given an integer array \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le n\))
Find the number of subarrays of \(a\) whose \(\operatorname{XOR}\) has an even number of divisors. In other words, find all pairs of indices \((i, j)\) (\(i \le j\)) such that \(a_i \oplus a_{i + 1} \oplus \dots \oplus a_j\) has an even number of divisors
For example, numbers \(2\), \(3\), \(5\) or \(6\) have an even number of divisors, while \(1\) and \(4\) — odd. Consider that \(0\) has an odd number of divisors in this task
Here \(\operatorname{XOR}\) (or \(\oplus\)) denotes the bitwise XOR operation
Print the number of subarrays but multiplied by 2022... Okay, let's stop. Just print the actual answer
Input
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \leq t \leq 10^4\)). Description of the test cases follows
The first line of each test case contains a single integer \(n\) (\(2 \leq n \leq 2 \cdot 10^5\)) — the length of the array \(a\)
The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (\(1 \leq a_i \leq n\))
It is guaranteed that the sum of \(n\) over all test cases does not exceed \(2 \cdot 10^5\)
Output
For each test case, print the number of subarrays, whose \(\operatorname{XOR}\) has an even number of divisors
Example
input
1 2 3 4 5 6 7 8 9
4 3 3 1 2 5 4 2 1 5 3 4 4 4 4 4 7 5 7 3 7 1 7 3
output
1 2 3 4
4 11 0 20
Note
In the first test case, there are \(4\) subarrays whose \(\operatorname{XOR}\) has an even number of divisors: \([3]\), \([3,1]\), \([1,2]\), \([2]\)
In the second test case, there are \(11\) subarrays whose \(\operatorname{XOR}\) has an even number of divisors: \([4,2]\), \([4,2,1]\), \([4,2,1,5]\), \([2]\), \([2,1]\), \([2,1,5]\), \([2,1,5,3]\), \([1,5,3]\), \([5]\), \([5,3]\), \([3]\)
In the third test case, there is no subarray whose \(\operatorname{XOR}\) has an even number of divisors since \(\operatorname{XOR}\) of any subarray is either \(4\) or \(0\)
Game studio "DbZ Games" wants to introduce another map in their popular game "Valiant". This time, the map named "Panvel" will be based on the city of Mumbai
Mumbai can be represented as \(n \times m\) cellular grid. Each cell \((i, j)\) (\(1 \le i \le n\); \(1 \le j \le m\)) of the grid is occupied by a cuboid building of height \(a_{i,j}\)
This time, DbZ Games want to make a map that has perfect vertical gameplay. That's why they want to choose an \(l \times l\) square inside Mumbai, such that each building inside the square has a height of at least \(l\)
Can you help DbZ Games find such a square of the maximum possible size \(l\)?
Input
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \leq t \leq 1000\)). Description of the test cases follows
The first line of each test case contains two positive integers \(n\) and \(m\) (\(1 \le n \le m\); \(1 \leq n \cdot m \leq 10^6\))
The \(i\)-th of next \(n\) lines contains \(m\) integers \(a_{i,1}, a_{i,2}, \dots, a_{i,m}\) (\(1 \leq a_{i,j} \leq 10^6\)) — heights of buildings on the \(i\)-th row
It's guaranteed that the sum of \(n \cdot m\) over all test cases doesn't exceed \(10^6\)
Output
For each test case, print the maximum side length \(l\) of the square DbZ Games can choose
In the first test case, we can choose the square of side \(l = 2\) (i. e. the whole grid) since the heights of all buildings are greater than or equal to \(2\)
In the second test case, we can only choose the side as \(1\), so the answer is \(1\)
In the third test case, there are no squares of size \(2\) that have all buildings of height at least \(2\), so the answer is \(1\)
public: RMQ_ST_2D() = delete; RMQ_ST_2D(query_func qfunc): qfunc(qfunc), f() {} template <typename init_func = std::function<data_t(size_t, size_t)>> voidinit(size_t n, size_t m, init_func ifunc) { constsize_t K = (size_t)std::log2(std::max(n, m)) + 1; f.resize(K); for (auto &i : f) { i.resize(n); for (auto &j : i) j.resize(m); } for (size_t i = 0; i < n; ++i) for (size_t j = 0; j < m; ++j) f[0][i][j] = ifunc(i, j); for (size_t k = 1, p = 1, q = 2; k < K; ++k, p = q, q *= 2) for (int i = 0; i + q - 1 < n; ++i) for (int j = 0; j + q - 1 < m; ++j) f[k][i][j] = qfunc(qfunc(f[k - 1][i][j], f[k - 1][i + p][j]), qfunc(f[k - 1][i][j + p], f[k - 1][i + p][j + p])); } data_tquery(size_t x, size_t y, size_t l)const{ size_t _ = (size_t)std::log2(l); returnqfunc(qfunc(f[_][x][y], f[_][x + l - (1 << _)][y]), qfunc(f[_][x][y + l - (1 << _)], f[_][x + l - (1 << _)][y + l - (1 << _)])); } }; autosolve([[maybe_unused]] int t_ = 0) -> void{ int n, m; cin >> n >> m; vvc<int> a(n, vc<int>(m)); for (auto &i : a) for (auto &j : i) cin >> j; RMQ_ST_2D<int> st([](int x, int y) { return min(x, y); }); st.init(n, m, [&](size_t x, size_t y) { return a[x][y]; }); auto check = [&](int g) { int mx = 0; for (int i = 0; i <= n - g; ++i) for (int j = 0; j <= m - g; ++j) mx = max(mx, st.query(i, j, g)); return mx >= g; }; int l = 1, r = min(n, m), ans = l; while (l <= r) { auto m = r - (r - l) / 2; if (check(m)) l = (ans = m) + 1; else r = m - 1; } cout << ans << '\n'; } intmain(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int i_ = 0; int t_ = 0; std::cin >> t_; for (i_ = 0; i_ < t_; ++i_) solve(i_); return0; }
E - Graph Cost
You are given an initially empty undirected graph with \(n\) nodes, numbered from \(1\) to \(n\) (i. e. \(n\) nodes and \(0\) edges). You want to add \(m\) edges to the graph, so the graph won't contain any self-loop or multiple edges
If an edge connecting two nodes \(u\) and \(v\) is added, its weight must be equal to the greatest common divisor of \(u\) and \(v\), i. e. \(\gcd(u, v)\)
In order to add edges to the graph, you can repeat the following process any number of times (possibly zero):
choose an integer \(k \ge 1\);
add exactly \(k\) edges to the graph, each having a weight equal to \(k + 1\). Adding these \(k\) edges costs \(k + 1\) in total
Note that you can't create self-loops or multiple edges. Also, if you can't add \(k\) edges of weight \(k + 1\), you can't choose such \(k\)
For example, if you can add \(5\) more edges to the graph of weight \(6\), you may add them, and it will cost \(6\) for the whole pack of \(5\) edges. But if you can only add \(4\) edges of weight \(6\) to the graph, you can't perform this operation for \(k = 5\)
Given two integers \(n\) and \(m\), find the minimum total cost to form a graph of \(n\) vertices and exactly \(m\) edges using the operation above. If such a graph can't be constructed, output \(-1\)
Note that the final graph may consist of several connected components
Input
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \leq t \leq 10^4\)). Description of the test cases follows
The first line of each test case contains two integers \(n\) and \(m\) (\(2 \leq n \leq 10^6\); \(1 \leq m \leq \frac{n(n-1)}{2}\))
It is guaranteed that the sum of \(n\) over all test cases does not exceed \(10^6\)
Output
For each test case, print the minimum cost to build the graph, or \(-1\) if you can't build such a graph
Example
input
1 2 3 4 5
4 4 1 6 10 9 4 10 11
output
1 2 3 4
2 -1 7 21
Note
In the first test case, we can add an edge between the vertices \(2\) and \(4\) with \(\gcd = 2\). This is the only possible way to add \(1\) edge that will cost \(2\)
In the second test case, there is no way to add \(10\) edges, so the answer is \(-1\)
In the third test case, we can add the following edges:
\(k = 1\): edge of weight \(2\) between vertices \(2\) and \(4\) (\(\gcd(2, 4) = 2\)). Cost: \(2\);
\(k = 1\): edge of weight \(2\) between vertices \(4\) and \(6\) (\(\gcd(4, 6) = 2\)). Cost: \(2\);
/* * @Author: Tifa * @Description: From <https://github.com/Tiphereth-A/CP-archives> * !!! ATTENEION: All the context below is licensed under a * GNU Affero General Public License, Version 3. * See <https://www.gnu.org/licenses/agpl-3.0.txt>. */ #include<bits/stdc++.h> template <classTp> using vc = std::vector<Tp>; structCustomHash { staticconstexpruint64_tsplitmix64(uint64_t x){ x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } staticconstexprsize_tappend(size_t x, size_t y){ return x ^ (y >> 1) ^ ((y & 1) << (sizeof(size_t) * 8 - 1)); } size_toperator()(uint64_t x)const{ staticconstuint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); returnsplitmix64(x + FIXED_RANDOM); } template <classTp, classUp> size_toperator()(std::pair<Tp, Up> const &p)const{ returnappend((*this)(p.first), (*this)(p.second)); } template <typename... Ts> size_toperator()(std::tuple<Ts...> const &tp)const{ size_t ret = 0; std::apply( [&](Ts const &...targs) { ((ret = append(ret, (*this)(targs))), ...); }, tp); return ret; } template < classTp, std::enable_if_t<std::is_same<decltype(std::declval<Tp>().begin()), typename Tp::iterator>::value && std::is_same<decltype(std::declval<Tp>().end()), typename Tp::iterator>::value> * = nullptr> size_toperator()(Tp const &tp) const { size_t ret = 0; for (auto &&i : tp) ret = append(ret, (*this)(i)); return ret; } }; using i64 = int64_t; #define for_(i, l, r, vars...) \ for (std::make_signed_t<decltype(l + r)> i = (l), i##end = (r), ##vars; \ i <= i##end; \ ++i) #define rfor_(i, r, l, vars...) \ for (std::make_signed_t<decltype(r - l)> i = (r), i##end = (l), ##vars; \ i >= i##end; \ --i) template <classTp> constexprautochkmin(Tp &a, Tp b) -> bool{ return b < a ? a = b, true : false; } template <classTp> constexprautochkmax(Tp &a, Tp b) -> bool{ return a < b ? a = b, true : false; } template <classTp> constexprautoispow2(Tp i) -> bool{ return i && (i & -i) == i; } #define TPL_SIZE_(Tuple) std::tuple_size_v<std::remove_reference_t<Tuple>> namespace tuple_detail_ { template <std::size_t Begin, classTuple, std::size_t... Is> constexprautosubtuple_impl_(Tuple &&t, std::index_sequence<Is...>){ return std::make_tuple(std::get<Is + Begin>(t)...); } template <classTuple, classBinOp, std::size_t... Is> constexprauto apply2_impl_(BinOp &&f, Tuple &&lhs, Tuple &&rhs, std::index_sequence<Is...>){ return std::make_tuple( std::forward<BinOp>(f)(std::get<Is>(lhs), std::get<Is>(rhs))...); } } // namespace tuple_detail_ template <std::size_t Begin, std::size_t Len, classTuple> constexprautosubtuple(Tuple &&t){ static_assert(Begin <= TPL_SIZE_(Tuple) && Len <= TPL_SIZE_(Tuple) && Begin + Len <= TPL_SIZE_(Tuple), "Out of range"); return tuple_detail_::subtuple_impl_<Begin>(t, std::make_index_sequence<Len>()); } template <std::size_t Pos, classTp, classTuple> constexprautotuple_push(Tp &&v, Tuple &&t){ static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple"); return std::tuple_cat(subtuple<0, Pos>(t), std::make_tuple(v), subtuple<Pos, TPL_SIZE_(Tuple) - Pos>(t)); } template <classTp, classTuple> constexprautotuple_push_front(Tp &&v, Tuple &&t){ returntuple_push<0>(v, t); } template <classTp, classTuple> constexprautotuple_push_back(Tp &&v, Tuple &&t){ returntuple_push<TPL_SIZE_(Tuple)>(v, t); } template <std::size_t Pos, classTuple> constexprautotuple_pop(Tuple &&t){ static_assert(TPL_SIZE_(Tuple) > 0, "Pop from empty tuple"); return std::tuple_cat(subtuple<0, Pos>(t), subtuple<Pos + 1, TPL_SIZE_(Tuple) - Pos - 1>(t)); } template <classTuple> constexprautotuple_pop_front(Tuple &&t){ returntuple_pop<0>(t); } template <classTuple> constexprautotuple_pop_back(Tuple &&t){ returntuple_pop<TPL_SIZE_(Tuple) - 1>(t); } template <classTuple, classBinOp> constexprautoapply2(BinOp &&f, Tuple &&lhs, Tuple &&rhs){ return tuple_detail_::apply2_impl_( f, lhs, rhs, std::make_index_sequence<TPL_SIZE_(Tuple)>()); } #define OO_PTEQ_(op) \ template <class Tp, class Up> \ constexpr auto operator op(std::pair<Tp, Up> lhs, \ const std::pair<Tp, Up> &rhs) { \ return std::pair<Tp, Up>{lhs.first op rhs.first, \ lhs.second op rhs.second}; \ } \ template <class... Ts> \ constexpr auto operator op(std::tuple<Ts...> const &lhs, \ std::tuple<Ts...> const &rhs) { \ return apply2([](auto &&l, auto &&r) { return l op r; }, lhs, rhs); \ } \ template <class Tp, class Up> \ constexpr std::pair<Tp, Up> &operator op##=(std::pair<Tp, Up> &lhs, \ const std::pair<Tp, Up> &rhs) { \ lhs.first op## = rhs.first; \ lhs.second op## = rhs.second; \ return lhs; \ } \ template <class... Ts> \ constexpr auto operator op##=(std::tuple<Ts...> &lhs, \ const std::tuple<Ts...> &rhs) { \ return lhs = lhs op rhs; \ } OO_PTEQ_(+) OO_PTEQ_(-) OO_PTEQ_(*) OO_PTEQ_(/) OO_PTEQ_(%) OO_PTEQ_(&) OO_PTEQ_(|) OO_PTEQ_(^) OO_PTEQ_(<<) OO_PTEQ_(>>) #undef OO_PTEQ_ #undef TPL_SIZE_ template <classTp, classUp> std::istream &operator>>(std::istream &is, std::pair<Tp, Up> &p) { return is >> p.first >> p.second; } template <classTp, classUp> std::ostream &operator<<(std::ostream &os, const std::pair<Tp, Up> &p) { return os << p.first << ' ' << p.second; } template <typename... Ts> std::istream &operator>>(std::istream &is, std::tuple<Ts...> &p) { std::apply([&](Ts &...targs) { ((is >> targs), ...); }, p); return is; } template <typename... Ts> std::ostream &operator<<(std::ostream &os, const std::tuple<Ts...> &p) { std::apply( [&](Ts const &...targs) { std::size_t n{0}; ((os << targs << (++n != sizeof...(Ts) ? " " : "")), ...); }, p); return os; } template < classCh, classTr, classCt, std::enable_if_t<std::is_same<decltype(std::declval<Ct>().begin()), typename Ct::iterator>::value && std::is_same<decltype(std::declval<Ct>().end()), typename Ct::iterator>::value> * = nullptr> std::basic_ostream<Ch, Tr> &operator<<(std::basic_ostream<Ch, Tr> &os, const Ct &x) { if (x.begin() == x.end()) return os; for (auto it = x.begin(); it != x.end() - 1; ++it) os << *it << ' '; os << x.back(); return os; } usingnamespace std; autosolve([[maybe_unused]] int t_ = 0) -> void{ i64 n, m; cin >> n >> m; vc<i64> f(n + 1); rfor_(i, n, 2) { f[i] = (n / i) * (n / i - 1) / 2; for_(j, 2, n / i) f[i] -= f[j * i]; } i64 ans = 0; rfor_(i, n, 2) { auto now = min(f[i], m) / (i - 1); ans += now * i; m -= now * (i - 1); if (!m) break; } cout << (m ? -1 : ans) << '\n'; } intmain(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int i_ = 0; int t_ = 0; std::cin >> t_; for (i_ = 0; i_ < t_; ++i_) solve(i_); return0; }
F - Function Sum
Suppose you have an integer array \(a_1, a_2, \dots, a_n\)
Let \(\operatorname{lsl}(i)\) be the number of indices \(j\) (\(1 \le j < i\)) such that \(a_j < a_i\)
Analogically, let \(\operatorname{grr}(i)\) be the number of indices \(j\) (\(i < j \le n\)) such that \(a_j > a_i\)
Let's name position \(i\) good in the array \(a\) if \(\operatorname{lsl}(i) < \operatorname{grr}(i)\)
Finally, let's define a function \(f\) on array \(a\)\(f(a)\) as the sum of all \(a_i\) such that \(i\) is good in \(a\)
Given two integers \(n\) and \(k\), find the sum of \(f(a)\) over all arrays \(a\) of size \(n\) such that \(1 \leq a_i \leq k\) for all \(1 \leq i \leq n\) modulo \(998\,244\,353\)
Input
The first and only line contains two integers \(n\) and \(k\) (\(1 \leq n \leq 50\); \(2 \leq k < 998\,244\,353\))
Output
Output a single integer — the sum of \(f\) over all arrays \(a\) of size \(n\) modulo \(998\,244\,353\)