比赛记录 - Codeforces Round #841 (Div. 2) and Divide by Zero 2022

Tifa's Blog

随笔 - 关于 C++ 模板的部分特化随笔 - Miller-Rabin + Pollard-Rho 分解质因子的时间复杂度分析随笔 - 批量重命名 APK 文件的 Python 脚本 VP 记录 - 2021 CCPC 哈尔滨站 VP 记录 - 2023 ICPC 亚洲区域赛 (南京) VP 记录 - 2023 CCPC 哈尔滨站 VP 记录 - 2023 CCPC 桂林站 VP 记录 - 2023 ICPC 亚洲区域赛 (网络预选赛 Ⅰ) VP 记录 - 2021 ICPC 亚洲区域赛 (澳门) 题解 - [Luogu P7486] 「Stoi2031」彩虹拟阵简介（unfin）题解 - [Luogu P5824] 十二重计数法随笔 - C++ 的高维向量 | Tifa's Blog 目录 - 算法竞赛模板 | Tifa's Blog 目录 - 学术垃圾 | Tifa's Blog 比赛记录 - Codeforces Round #842 (Div. 2) 比赛记录 - Hello 2023 | Tifa's Blog 随笔 - C++ 基于标签分发的线性筛 | Tifa's Blog VP 记录 - 2022 ICPC 亚洲区域赛 (杭州) VP 记录 - 2022 ICPC 亚洲区域赛 (济南)

Tifa · 2022-12-29 · via Tifa's Blog

比赛链接

进度: 6 / 6

A - Joey Takes Money

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

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\).

\[ [2, 3, 2] \xrightarrow[x = 6,\; y = 1]{i = 1,\; j = 2} [6, 1, 2] \]
He chooses \(i = 1\) and \(j = 3\) (so he has \(a[i] \cdot a[j] = 12\)), chooses \(x = 12\) and \(y = 1\) and makes \(a[i] = 12\) and \(a[j] = 1\).

\[ [6, 1, 2] \xrightarrow[x = 12,\; y = 1]{i = 1,\; j = 3} [12, 1, 1] \]

The sum is \(14\) which is the maximum of all possible sums. The answer is \(2022 \cdot 14 = 28308\)

代码参考

CodeForces_1731Aview raw








#include <bits/stdc++.h>
template <class Tp>
using vc = std::vector<Tp>;
struct CustomHash {
  static constexpr uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  static constexpr size_t append(size_t x, size_t y) {
    return x ^ (y >> 1) ^ ((y & 1) << (sizeof(size_t) * 8 - 1));
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
      std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
  template <class Tp, class Up>
  size_t operator()(std::pair<Tp, Up> const &p) const {
    return append((*this)(p.first), (*this)(p.second));
  }
  template <typename... Ts>
  size_t operator()(std::tuple<Ts...> const &tp) const {
    size_t ret = 0;
    std::apply(
      [&](Ts const &...targs) { ((ret = append(ret, (*this)(targs))), ...); },
      tp);
    return ret;
  }
  template <
    class Tp,
    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_t operator()(Tp const &tp) const {
    size_t ret = 0;
    for (auto &&i : tp) ret = append(ret, (*this)(i));
    return ret;
  }
};
using i64 = int64_t;
using i128 = __int128_t;
#define foreach_ref_(i, container) for (auto &i : (container))
#define all_(a) (a).begin(), (a).end()
#define read_var_(type, name) \
  type name;                  \
  std::cin >> name
#define read_container_(type, name, size) \
  type name(size);                        \
  foreach_ref_(i, name) std::cin >> i
template <class Tp>
constexpr auto chkmin(Tp &a, Tp b) -> bool {
  return b < a ? a = b, true : false;
}
template <class Tp>
constexpr auto chkmax(Tp &a, Tp b) -> bool {
  return a < b ? a = b, true : false;
}
template <class Tp>
constexpr auto ispow2(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, class Tuple, std::size_t... Is>
constexpr auto subtuple_impl_(Tuple &&t, std::index_sequence<Is...>) {
  return std::make_tuple(std::get<Is + Begin>(t)...);
}
template <class Tuple, class BinOp, std::size_t... Is>
constexpr auto
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))...);
}
}  
template <std::size_t Begin, std::size_t Len, class Tuple>
constexpr auto subtuple(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, class Tp, class Tuple>
constexpr auto tuple_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 <class Tp, class Tuple>
constexpr auto tuple_push_front(Tp &&v, Tuple &&t) {
  return tuple_push<0>(v, t);
}
template <class Tp, class Tuple>
constexpr auto tuple_push_back(Tp &&v, Tuple &&t) {
  return tuple_push<TPL_SIZE_(Tuple)>(v, t);
}
template <std::size_t Pos, class Tuple>
constexpr auto tuple_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 <class Tuple>
constexpr auto tuple_pop_front(Tuple &&t) {
  return tuple_pop<0>(t);
}
template <class Tuple>
constexpr auto tuple_pop_back(Tuple &&t) {
  return tuple_pop<TPL_SIZE_(Tuple) - 1>(t);
}
template <class Tuple, class BinOp>
constexpr auto apply2(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 <class Tp, class Up>
std::istream &operator>>(std::istream &is, std::pair<Tp, Up> &p) {
  return is >> p.first >> p.second;
}
template <class Tp, class Up>
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 <
  class Ch,
  class Tr,
  class Ct,
  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;
}
using namespace std;
ostream &operator<<(ostream &os, i128 n) {
  if (n < 0) {
    os << '-';
    n = -n;
  }
  if (n > 9) os << (i128)(n / 10);
  os << (uint_fast16_t)(n % 10);
  return os;
}
auto solve([[maybe_unused]] int t_ = 0) -> void {
  read_var_(int, n);
  read_container_(vc<i64>, a, n);
  i128 ans = accumulate(all_(a), (i128)1, multiplies<i64>());
  cout << 2022 * (ans + n - 1) << '\n';
}
int main() {
  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_);
  return 0;
}

B - Kill Demodogs

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

output

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\)

代码参考

CodeForces_1731Bview raw








#include <bits/stdc++.h>
struct CustomHash {
  static constexpr uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  static constexpr size_t append(size_t x, size_t y) {
    return x ^ (y >> 1) ^ ((y & 1) << (sizeof(size_t) * 8 - 1));
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
      std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
  template <class Tp, class Up>
  size_t operator()(std::pair<Tp, Up> const &p) const {
    return append((*this)(p.first), (*this)(p.second));
  }
  template <typename... Ts>
  size_t operator()(std::tuple<Ts...> const &tp) const {
    size_t ret = 0;
    std::apply(
      [&](Ts const &...targs) { ((ret = append(ret, (*this)(targs))), ...); },
      tp);
    return ret;
  }
  template <
    class Tp,
    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_t operator()(Tp const &tp) const {
    size_t ret = 0;
    for (auto &&i : tp) ret = append(ret, (*this)(i));
    return ret;
  }
};
using i64 = int64_t;
using i128 = __int128_t;
#define read_var_(type, name) \
  type name;                  \
  std::cin >> name
template <class Tp>
constexpr auto chkmin(Tp &a, Tp b) -> bool {
  return b < a ? a = b, true : false;
}
template <class Tp>
constexpr auto chkmax(Tp &a, Tp b) -> bool {
  return a < b ? a = b, true : false;
}
template <class Tp>
constexpr auto ispow2(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, class Tuple, std::size_t... Is>
constexpr auto subtuple_impl_(Tuple &&t, std::index_sequence<Is...>) {
  return std::make_tuple(std::get<Is + Begin>(t)...);
}
template <class Tuple, class BinOp, std::size_t... Is>
constexpr auto
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))...);
}
}  
template <std::size_t Begin, std::size_t Len, class Tuple>
constexpr auto subtuple(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, class Tp, class Tuple>
constexpr auto tuple_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 <class Tp, class Tuple>
constexpr auto tuple_push_front(Tp &&v, Tuple &&t) {
  return tuple_push<0>(v, t);
}
template <class Tp, class Tuple>
constexpr auto tuple_push_back(Tp &&v, Tuple &&t) {
  return tuple_push<TPL_SIZE_(Tuple)>(v, t);
}
template <std::size_t Pos, class Tuple>
constexpr auto tuple_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 <class Tuple>
constexpr auto tuple_pop_front(Tuple &&t) {
  return tuple_pop<0>(t);
}
template <class Tuple>
constexpr auto tuple_pop_back(Tuple &&t) {
  return tuple_pop<TPL_SIZE_(Tuple) - 1>(t);
}
template <class Tuple, class BinOp>
constexpr auto apply2(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 <class Tp, class Up>
std::istream &operator>>(std::istream &is, std::pair<Tp, Up> &p) {
  return is >> p.first >> p.second;
}
template <class Tp, class Up>
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 <
  class Ch,
  class Tr,
  class Ct,
  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;
}
const i64 MOD = 1e9 + 7;
using namespace std;
ostream &operator<<(ostream &os, i128 n) {
  if (n < 0) {
    os << '-';
    n = -n;
  }
  if (n > 9) os << (i128)(n / 10);
  os << (uint_fast16_t)(n % 10);
  return os;
}
auto solve([[maybe_unused]] int t_ = 0) -> void {
  read_var_(i64, n);
  i128 ans = (i128)n * (n + 1) / 2 * (2 * n + 1) / 3 % MOD;
  ans += (i128)(n - 1) * n * (n + 1) / 3 % MOD;
  cout << 2022 * ans % MOD << '\n';
}
int main() {
  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_);
  return 0;
}

C - Even Subarrays

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

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

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\)

代码参考

CodeForces_1731Cview raw








#include <bits/stdc++.h>
template <class Tp>
using vc = std::vector<Tp>;
struct CustomHash {
  static constexpr uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  static constexpr size_t append(size_t x, size_t y) {
    return x ^ (y >> 1) ^ ((y & 1) << (sizeof(size_t) * 8 - 1));
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
      std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
  template <class Tp, class Up>
  size_t operator()(std::pair<Tp, Up> const &p) const {
    return append((*this)(p.first), (*this)(p.second));
  }
  template <typename... Ts>
  size_t operator()(std::tuple<Ts...> const &tp) const {
    size_t ret = 0;
    std::apply(
      [&](Ts const &...targs) { ((ret = append(ret, (*this)(targs))), ...); },
      tp);
    return ret;
  }
  template <
    class Tp,
    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_t operator()(Tp const &tp) const {
    size_t ret = 0;
    for (auto &&i : tp) ret = append(ret, (*this)(i));
    return ret;
  }
};
using i64 = int64_t;
using i128 = __int128_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 read_var_(type, name) \
  type name;                  \
  std::cin >> name
template <class Tp>
constexpr auto chkmin(Tp &a, Tp b) -> bool {
  return b < a ? a = b, true : false;
}
template <class Tp>
constexpr auto chkmax(Tp &a, Tp b) -> bool {
  return a < b ? a = b, true : false;
}
template <class Tp>
constexpr auto ispow2(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, class Tuple, std::size_t... Is>
constexpr auto subtuple_impl_(Tuple &&t, std::index_sequence<Is...>) {
  return std::make_tuple(std::get<Is + Begin>(t)...);
}
template <class Tuple, class BinOp, std::size_t... Is>
constexpr auto
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))...);
}
}  
template <std::size_t Begin, std::size_t Len, class Tuple>
constexpr auto subtuple(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, class Tp, class Tuple>
constexpr auto tuple_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 <class Tp, class Tuple>
constexpr auto tuple_push_front(Tp &&v, Tuple &&t) {
  return tuple_push<0>(v, t);
}
template <class Tp, class Tuple>
constexpr auto tuple_push_back(Tp &&v, Tuple &&t) {
  return tuple_push<TPL_SIZE_(Tuple)>(v, t);
}
template <std::size_t Pos, class Tuple>
constexpr auto tuple_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 <class Tuple>
constexpr auto tuple_pop_front(Tuple &&t) {
  return tuple_pop<0>(t);
}
template <class Tuple>
constexpr auto tuple_pop_back(Tuple &&t) {
  return tuple_pop<TPL_SIZE_(Tuple) - 1>(t);
}
template <class Tuple, class BinOp>
constexpr auto apply2(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 <class Tp, class Up>
std::istream &operator>>(std::istream &is, std::pair<Tp, Up> &p) {
  return is >> p.first >> p.second;
}
template <class Tp, class Up>
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 <
  class Ch,
  class Tr,
  class Ct,
  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;
}
using namespace std;
ostream &operator<<(ostream &os, i128 n) {
  if (n < 0) {
    os << '-';
    n = -n;
  }
  if (n > 9) os << (i128)(n / 10);
  os << (uint_fast16_t)(n % 10);
  return os;
}
auto solve([[maybe_unused]] int t_ = 0) -> void {
  read_var_(i64, n);
  vc<i64> a(n + 1);
  for_(i, 1, n) cin >> a[i];
  vc<i64> sum = a;
  for_(i, 1, n) sum[i] ^= sum[i - 1];
  i64 nn = (1ll << (64 - __builtin_clzll(n)));
  vc<i64> vis(nn);
  for (auto j : sum) ++vis[j];
  i64 ans = 0;
  for_(i, 0, nn - 1) ans += vis[i] * (vis[i] - 1) / 2;
  vc<i64> sum2 = sum;
  for_(i, 1, nn, ii) {
    if ((ii = i * i) >= nn) break;
    for (auto &j : sum2) j ^= ii;
    vc<int> vis2(nn);
    for (auto j : sum2) ++vis2[j];
    i64 ans2 = 0;
    for_(j, 0, nn - 1) ans2 += vis[j] * vis2[j];
    for (auto &j : sum2) j ^= ii;
    ans += ans2 / 2;
  }
  cout << n * (n + 1) / 2 - ans << '\n';
}
int main() {
  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_);
  return 0;
}

D - Valiant’s New Map

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

Example

input

4
2 2
2 3
4 5
1 3
1 2 3
2 3
4 4 3
2 1 4
5 6
1 9 4 6 5 8
10 9 5 8 11 6
24 42 32 8 11 1
23 1 9 69 13 3
13 22 60 12 14 17

output

Note

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\)

代码参考

CodeForces_1731Dview raw








#include <bits/stdc++.h>
template <class Tp>
using vc = std::vector<Tp>;
template <class Tp>
using vvc = std::vector<std::vector<Tp>>;
struct CustomHash {
  static constexpr uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  static constexpr size_t append(size_t x, size_t y) {
    return x ^ (y >> 1) ^ ((y & 1) << (sizeof(size_t) * 8 - 1));
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
      std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
  template <class Tp, class Up>
  size_t operator()(std::pair<Tp, Up> const &p) const {
    return append((*this)(p.first), (*this)(p.second));
  }
  template <typename... Ts>
  size_t operator()(std::tuple<Ts...> const &tp) const {
    size_t ret = 0;
    std::apply(
      [&](Ts const &...targs) { ((ret = append(ret, (*this)(targs))), ...); },
      tp);
    return ret;
  }
  template <
    class Tp,
    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_t operator()(Tp const &tp) const {
    size_t ret = 0;
    for (auto &&i : tp) ret = append(ret, (*this)(i));
    return ret;
  }
};
using u32 = uint32_t;
template <class Tp>
constexpr auto chkmin(Tp &a, Tp b) -> bool {
  return b < a ? a = b, true : false;
}
template <class Tp>
constexpr auto chkmax(Tp &a, Tp b) -> bool {
  return a < b ? a = b, true : false;
}
template <class Tp>
constexpr auto ispow2(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, class Tuple, std::size_t... Is>
constexpr auto subtuple_impl_(Tuple &&t, std::index_sequence<Is...>) {
  return std::make_tuple(std::get<Is + Begin>(t)...);
}
template <class Tuple, class BinOp, std::size_t... Is>
constexpr auto
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))...);
}
}  
template <std::size_t Begin, std::size_t Len, class Tuple>
constexpr auto subtuple(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, class Tp, class Tuple>
constexpr auto tuple_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 <class Tp, class Tuple>
constexpr auto tuple_push_front(Tp &&v, Tuple &&t) {
  return tuple_push<0>(v, t);
}
template <class Tp, class Tuple>
constexpr auto tuple_push_back(Tp &&v, Tuple &&t) {
  return tuple_push<TPL_SIZE_(Tuple)>(v, t);
}
template <std::size_t Pos, class Tuple>
constexpr auto tuple_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 <class Tuple>
constexpr auto tuple_pop_front(Tuple &&t) {
  return tuple_pop<0>(t);
}
template <class Tuple>
constexpr auto tuple_pop_back(Tuple &&t) {
  return tuple_pop<TPL_SIZE_(Tuple) - 1>(t);
}
template <class Tuple, class BinOp>
constexpr auto apply2(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 <class Tp, class Up>
std::istream &operator>>(std::istream &is, std::pair<Tp, Up> &p) {
  return is >> p.first >> p.second;
}
template <class Tp, class Up>
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 <
  class Ch,
  class Tr,
  class Ct,
  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;
}
const u32 K = 21;
using namespace std;
template <typename data_t,
          typename query_func =
            std::function<data_t(const data_t &, const data_t &)>>
class RMQ_ST_2D {
protected:
  query_func qfunc;
  std::vector<std::vector<std::vector<data_t>>> f;

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)>>
  void init(size_t n, size_t m, init_func ifunc) {
    const size_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_t query(size_t x, size_t y, size_t l) const {
    size_t _ = (size_t)std::log2(l);
    return qfunc(qfunc(f[_][x][y], f[_][x + l - (1 << _)][y]),
                 qfunc(f[_][x][y + l - (1 << _)],
                       f[_][x + l - (1 << _)][y + l - (1 << _)]));
  }
};
auto solve([[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';
}
int main() {
  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_);
  return 0;
}

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

output

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\);
\(k = 2\): edges of weight \(3\): \((3, 6)\) and \((3, 9)\) (\(\gcd(3, 6) = \gcd(3, 9) = 3\)). Cost: \(3\)

As a result, we added \(1 + 1 + 2 = 4\) edges with total cost \(2 + 2 + 3 = 7\), which is the minimal possible cost

代码参考

CodeForces_1731Eview raw








#include <bits/stdc++.h>
template <class Tp>
using vc = std::vector<Tp>;
struct CustomHash {
  static constexpr uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  static constexpr size_t append(size_t x, size_t y) {
    return x ^ (y >> 1) ^ ((y & 1) << (sizeof(size_t) * 8 - 1));
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
      std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
  template <class Tp, class Up>
  size_t operator()(std::pair<Tp, Up> const &p) const {
    return append((*this)(p.first), (*this)(p.second));
  }
  template <typename... Ts>
  size_t operator()(std::tuple<Ts...> const &tp) const {
    size_t ret = 0;
    std::apply(
      [&](Ts const &...targs) { ((ret = append(ret, (*this)(targs))), ...); },
      tp);
    return ret;
  }
  template <
    class Tp,
    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_t operator()(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 <class Tp>
constexpr auto chkmin(Tp &a, Tp b) -> bool {
  return b < a ? a = b, true : false;
}
template <class Tp>
constexpr auto chkmax(Tp &a, Tp b) -> bool {
  return a < b ? a = b, true : false;
}
template <class Tp>
constexpr auto ispow2(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, class Tuple, std::size_t... Is>
constexpr auto subtuple_impl_(Tuple &&t, std::index_sequence<Is...>) {
  return std::make_tuple(std::get<Is + Begin>(t)...);
}
template <class Tuple, class BinOp, std::size_t... Is>
constexpr auto
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))...);
}
}  
template <std::size_t Begin, std::size_t Len, class Tuple>
constexpr auto subtuple(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, class Tp, class Tuple>
constexpr auto tuple_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 <class Tp, class Tuple>
constexpr auto tuple_push_front(Tp &&v, Tuple &&t) {
  return tuple_push<0>(v, t);
}
template <class Tp, class Tuple>
constexpr auto tuple_push_back(Tp &&v, Tuple &&t) {
  return tuple_push<TPL_SIZE_(Tuple)>(v, t);
}
template <std::size_t Pos, class Tuple>
constexpr auto tuple_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 <class Tuple>
constexpr auto tuple_pop_front(Tuple &&t) {
  return tuple_pop<0>(t);
}
template <class Tuple>
constexpr auto tuple_pop_back(Tuple &&t) {
  return tuple_pop<TPL_SIZE_(Tuple) - 1>(t);
}
template <class Tuple, class BinOp>
constexpr auto apply2(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 <class Tp, class Up>
std::istream &operator>>(std::istream &is, std::pair<Tp, Up> &p) {
  return is >> p.first >> p.second;
}
template <class Tp, class Up>
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 <
  class Ch,
  class Tr,
  class Ct,
  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;
}
using namespace std;
auto solve([[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';
}
int main() {
  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_);
  return 0;
}

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\)

Examples

input

3 3

output

input

5 6

output

input

12 30

output

920711694

Note

In the first test case:

\[ \begin{array}{c|c} f([1,1,1]) = 0&f([2,2,3]) = 2 + 2 = 4\\ f([1,1,2]) = 1 + 1 = 2&f([2,3,1]) = 2\\ f([1,1,3]) = 1 + 1 = 2&f([2,3,2]) = 2\\ f([1,2,1]) = 1&f([2,3,3]) = 2\\ f([1,2,2]) = 1&f([3,1,1]) = 0\\ f([1,2,3]) = 1&f([3,1,2]) = 1\\ f([1,3,1]) = 1&f([3,1,3]) = 1\\ f([1,3,2]) = 1&f([3,2,1]) = 0\\ f([1,3,3]) = 1&f([3,2,2]) = 0\\ f([2,1,1]) = 0&f([3,2,3]) = 2\\ f([2,1,2]) = 1&f([3,3,1]) = 0\\ f([2,1,3]) = 2 + 1 = 3&f([3,3,2]) = 0\\ f([2,2,1]) = 0&f([3,3,3]) = 0\\ f([2,2,2]) = 0\\ \end{array} \]

Adding up all of these values, we get \(28\) as the answer

代码参考

CodeForces_1731Fview raw








#include <bits/stdc++.h>
template <class Tp>
using vc = std::vector<Tp>;
struct CustomHash {
  static constexpr uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  static constexpr size_t append(size_t x, size_t y) {
    return x ^ (y >> 1) ^ ((y & 1) << (sizeof(size_t) * 8 - 1));
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
      std::chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
  template <class Tp, class Up>
  size_t operator()(std::pair<Tp, Up> const &p) const {
    return append((*this)(p.first), (*this)(p.second));
  }
  template <typename... Ts>
  size_t operator()(std::tuple<Ts...> const &tp) const {
    size_t ret = 0;
    std::apply(
      [&](Ts const &...targs) { ((ret = append(ret, (*this)(targs))), ...); },
      tp);
    return ret;
  }
  template <
    class Tp,
    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_t operator()(Tp const &tp) const {
    size_t ret = 0;
    for (auto &&i : tp) ret = append(ret, (*this)(i));
    return ret;
  }
};
using u32 = uint32_t;
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 all_(a) (a).begin(), (a).end()
template <class Tp>
constexpr auto chkmin(Tp &a, Tp b) -> bool {
  return b < a ? a = b, true : false;
}
template <class Tp>
constexpr auto chkmax(Tp &a, Tp b) -> bool {
  return a < b ? a = b, true : false;
}
template <class Tp>
constexpr auto ispow2(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, class Tuple, std::size_t... Is>
constexpr auto subtuple_impl_(Tuple &&t, std::index_sequence<Is...>) {
  return std::make_tuple(std::get<Is + Begin>(t)...);
}
template <class Tuple, class BinOp, std::size_t... Is>
constexpr auto
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))...);
}
}  
template <std::size_t Begin, std::size_t Len, class Tuple>
constexpr auto subtuple(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, class Tp, class Tuple>
constexpr auto tuple_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 <class Tp, class Tuple>
constexpr auto tuple_push_front(Tp &&v, Tuple &&t) {
  return tuple_push<0>(v, t);
}
template <class Tp, class Tuple>
constexpr auto tuple_push_back(Tp &&v, Tuple &&t) {
  return tuple_push<TPL_SIZE_(Tuple)>(v, t);
}
template <std::size_t Pos, class Tuple>
constexpr auto tuple_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 <class Tuple>
constexpr auto tuple_pop_front(Tuple &&t) {
  return tuple_pop<0>(t);
}
template <class Tuple>
constexpr auto tuple_pop_back(Tuple &&t) {
  return tuple_pop<TPL_SIZE_(Tuple) - 1>(t);
}
template <class Tuple, class BinOp>
constexpr auto apply2(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 <class Tp, class Up>
std::istream &operator>>(std::istream &is, std::pair<Tp, Up> &p) {
  return is >> p.first >> p.second;
}
template <class Tp, class Up>
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 <
  class Ch,
  class Tr,
  class Ct,
  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;
}
const u32 OFFSET = 5;
const u32 N = 5e5 + OFFSET;
const i64 MOD = 998244353;
using namespace std;
constexpr int64_t qpow(int64_t a, int64_t b, int64_t mod) {
  int64_t res(1);
  a %= mod;
  for (; b; b >>= 1, (a *= a) %= mod)
    if (b & 1) (res *= a) %= mod;
  return res;
}
constexpr int64_t inverse(int64_t n, int64_t mod) {
  int64_t b = mod, m0 = 0;
  for (int64_t q = 0, _ = 0, m1 = 1; n;) {
    _ = b - n * (q = b / n);
    b = n;
    n = _;
    _ = m0 - m1 * q;
    m0 = m1;
    m1 = _;
  }
  return (m0 + (m0 < 0 ? mod / b : 0)) % mod;
}
std::vector<int64_t> fact, inv_fact;
void init_fact(int64_t n = N, int64_t mod = MOD) {
  std::vector<int64_t> ffact(n);
  fact.resize(n * 2);
  inv_fact.resize(n);
  ffact[0] = fact[0] = inv_fact[0] = fact[1] = inv_fact[1] = 1;
  for (size_t i = 2; i < std::min(mod, n * 2); ++i)
    fact[i] = fact[i - 1] * i % mod;
  for (size_t i = 1; i < std::min(mod, n); ++i)
    ffact[i] = ffact[i - 1] * fact[i] % mod;
  int64_t _ = inverse(ffact[std::min(mod, n) - 1], mod);
  for (ptrdiff_t i = std::min(mod, n) - 1; i > 1; --i) {
    inv_fact[i] = _ * ffact[i - 1] % mod;
    _ = _ * fact[i] % mod;
  }
}
constexpr int64_t mCn(int m, int n, int64_t mod = MOD) {
  return m < n || n < 0 ? 0 :
                          fact[m] * inv_fact[n] % mod * inv_fact[m - n] % mod;
}
int64_t lagrange_interp_fixed_key(std::vector<int64_t> const &v,
                                  uint64_t x,
                                  int64_t mod) {
  const size_t n = v.size();
  if (x < n) return v[x];
  std::vector<int64_t> ifact(n);
  ifact[0] = ifact[1] = 1;
  for (size_t i = 2; i < n; ++i)
    ifact[i] = mod - mod / i * ifact[mod % i] % mod;
  for (size_t i = 3; i < n; ++i) (ifact[i] *= ifact[i - 1]) %= mod;
  std::vector<int64_t> pre(n);
  for (size_t i = 0; i < n; ++i) pre[i] = x - i;
  for (size_t i = 1; i < n; ++i) (pre[i] *= pre[i - 1]) %= mod;
  std::vector<int64_t> suc(n);
  for (size_t i = 0; i < n; ++i) suc[i] = x - i;
  for (ptrdiff_t i = n - 2; i >= 0; --i) (suc[i] *= suc[i + 1]) %= mod;
  int64_t ans = 0;
  for (size_t i = 0; i < n; ++i) {
    int64_t _ = v[i];
    if (i) _ = _ * pre[i - 1] % mod;
    if (i + 1 < n) _ = _ * suc[i + 1] % mod;
    _ = _ * ifact[i] % mod * ifact[n - i - 1] % mod;
    ans = (ans + ((n - i) % 2 ? _ : mod - _)) % mod;
  }
  return ans;
}
auto solve([[maybe_unused]] int t_ = 0) -> void {
  i64 n, k;
  cin >> n >> k;
  i64 ans = 0;
  vc<i64> f(n + 3);
  for_(i, 1, n)
    for_(x, 0, i - 1)
      for_(y, x + 1, n - i)
        for_(t, 1, n + 2)
          (f[t] += t * mCn(i - 1, x) % MOD * qpow(t - 1, x, MOD) % MOD *
                   qpow(k - t + 1, i - x - 1, MOD) % MOD * mCn(n - i, y) % MOD *
                   qpow(k - t, y, MOD) % MOD * qpow(t, n - i - y, MOD) % MOD) %=
            MOD;
  partial_sum(all_(f), f.begin(), [](i64 x, i64 y) { return (x + y) % MOD; });
  cout << lagrange_interp_fixed_key(f, k, MOD);
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int i_ = 0;
  init_fact();
  solve(i_);
  return 0;
}

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

Tifa's Blog

A - Joey Takes Money

Input

Output

Example

input

output

Note

代码参考

B - Kill Demodogs

Input

Output

Example

input

output

Note

代码参考

C - Even Subarrays

Input

Output

Example

input

output

Note

代码参考

D - Valiant’s New Map

Input

Output

Example

input

output

Note

代码参考

E - Graph Cost

Input

Output

Example

input

output

Note

代码参考

F - Function Sum

Input

Output

Examples

input

output

input

output

input

output

Note

代码参考