fork download
copy 
  1. /*
  2.   Compete against Yourself.
  3.   Author - Aryan (@aryanc403)
  4. */
  5. /*
  6.   Credits -
  7.   Atcoder library - https://a...content-available-to-author-only...b.io/ac-library/production/document_en/ (namespace atcoder)
  8.   Github source code of library - https://g...content-available-to-author-only...b.com/atcoder/ac-library/tree/master/atcoder
  9.   https://c...content-available-to-author-only...s.com/contest/4/submission/150120627
  10. */
  11. #include <bits/stdc++.h>
  12.  
  13. #include <cassert>
  14. #include <numeric>
  15. #include <type_traits>
  16.  
  17. #ifdef _MSC_VER
  18. #include <intrin.h>
  19. #endif
  20.  
  21.  
  22. #include <utility>
  23.  
  24. #ifdef _MSC_VER
  25. #include <intrin.h>
  26. #endif
  27.  
  28. namespace atcoder {
  29.  
  30. namespace internal {
  31.  
  32. constexpr long long safe_mod(long long x, long long m) {
  33.     x %= m;
  34.     if (x < 0) x += m;
  35.     return x;
  36. }
  37.  
  38. struct barrett {
  39.     unsigned int _m;
  40.     unsigned long long im;
  41.  
  42.     explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}
  43.  
  44.     unsigned int umod() const { return _m; }
  45.  
  46.     unsigned int mul(unsigned int a, unsigned int b) const {
  47.  
  48.         unsigned long long z = a;
  49.         z *= b;
  50. #ifdef _MSC_VER
  51.         unsigned long long x;
  52.         _umul128(z, im, &x);
  53. #else
  54.         unsigned long long x =
  55.             (unsigned long long)(((unsigned __int128)(z)*im) >> 64);
  56. #endif
  57.         unsigned long long y = x * _m;
  58.         return (unsigned int)(z - y + (z < y ? _m : 0));
  59.     }
  60. };
  61.  
  62. constexpr long long pow_mod_constexpr(long long x, long long n, int m) {
  63.     if (m == 1) return 0;
  64.     unsigned int _m = (unsigned int)(m);
  65.     unsigned long long r = 1;
  66.     unsigned long long y = safe_mod(x, m);
  67.     while (n) {
  68.         if (n & 1) r = (r * y) % _m;
  69.         y = (y * y) % _m;
  70.         n >>= 1;
  71.     }
  72.     return r;
  73. }
  74.  
  75. constexpr bool is_prime_constexpr(int n) {
  76.     if (n <= 1) return false;
  77.     if (n == 2 || n == 7 || n == 61) return true;
  78.     if (n % 2 == 0) return false;
  79.     long long d = n - 1;
  80.     while (d % 2 == 0) d /= 2;
  81.     constexpr long long bases[3] = {2, 7, 61};
  82.     for (long long a : bases) {
  83.         long long t = d;
  84.         long long y = pow_mod_constexpr(a, t, n);
  85.         while (t != n - 1 && y != 1 && y != n - 1) {
  86.             y = y * y % n;
  87.             t <<= 1;
  88.         }
  89.         if (y != n - 1 && t % 2 == 0) {
  90.             return false;
  91.         }
  92.     }
  93.     return true;
  94. }
  95. template <int n> constexpr bool is_prime = is_prime_constexpr(n);
  96.  
  97. constexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {
  98.     a = safe_mod(a, b);
  99.     if (a == 0) return {b, 0};
  100.  
  101.     long long s = b, t = a;
  102.     long long m0 = 0, m1 = 1;
  103.  
  104.     while (t) {
  105.         long long u = s / t;
  106.         s -= t * u;
  107.         m0 -= m1 * u;  // |m1 * u| <= |m1| * s <= b
  108.  
  109.  
  110.         auto tmp = s;
  111.         s = t;
  112.         t = tmp;
  113.         tmp = m0;
  114.         m0 = m1;
  115.         m1 = tmp;
  116.     }
  117.     if (m0 < 0) m0 += b / s;
  118.     return {s, m0};
  119. }
  120.  
  121. constexpr int primitive_root_constexpr(int m) {
  122.     if (m == 2) return 1;
  123.     if (m == 167772161) return 3;
  124.     if (m == 469762049) return 3;
  125.     if (m == 754974721) return 11;
  126.     if (m == 998244353) return 3;
  127.     int divs[20] = {};
  128.     divs[0] = 2;
  129.     int cnt = 1;
  130.     int x = (m - 1) / 2;
  131.     while (x % 2 == 0) x /= 2;
  132.     for (int i = 3; (long long)(i)*i <= x; i += 2) {
  133.         if (x % i == 0) {
  134.             divs[cnt++] = i;
  135.             while (x % i == 0) {
  136.                 x /= i;
  137.             }
  138.         }
  139.     }
  140.     if (x > 1) {
  141.         divs[cnt++] = x;
  142.     }
  143.     for (int g = 2;; g++) {
  144.         bool ok = true;
  145.         for (int i = 0; i < cnt; i++) {
  146.             if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
  147.                 ok = false;
  148.                 break;
  149.             }
  150.         }
  151.         if (ok) return g;
  152.     }
  153. }
  154. template <int m> constexpr int primitive_root = primitive_root_constexpr(m);
  155.  
  156. unsigned long long floor_sum_unsigned(unsigned long long n,
  157.                                       unsigned long long m,
  158.                                       unsigned long long a,
  159.                                       unsigned long long b) {
  160.     unsigned long long ans = 0;
  161.     while (true) {
  162.         if (a >= m) {
  163.             ans += n * (n - 1) / 2 * (a / m);
  164.             a %= m;
  165.         }
  166.         if (b >= m) {
  167.             ans += n * (b / m);
  168.             b %= m;
  169.         }
  170.  
  171.         unsigned long long y_max = a * n + b;
  172.         if (y_max < m) break;
  173.         n = (unsigned long long)(y_max / m);
  174.         b = (unsigned long long)(y_max % m);
  175.         std::swap(m, a);
  176.     }
  177.     return ans;
  178. }
  179.  
  180. }  // namespace internal
  181.  
  182. }  // namespace atcoder
  183.  
  184.  
  185. #include <cassert>
  186. #include <numeric>
  187. #include <type_traits>
  188.  
  189. namespace atcoder {
  190.  
  191. namespace internal {
  192.  
  193. #ifndef _MSC_VER
  194. template <class T>
  195. using is_signed_int128 =
  196.     typename std::conditional<std::is_same<T, __int128_t>::value ||
  197.                                   std::is_same<T, __int128>::value,
  198.                               std::true_type,
  199.                               std::false_type>::type;
  200.  
  201. template <class T>
  202. using is_unsigned_int128 =
  203.     typename std::conditional<std::is_same<T, __uint128_t>::value ||
  204.                                   std::is_same<T, unsigned __int128>::value,
  205.                               std::true_type,
  206.                               std::false_type>::type;
  207.  
  208. template <class T>
  209. using make_unsigned_int128 =
  210.     typename std::conditional<std::is_same<T, __int128_t>::value,
  211.                               __uint128_t,
  212.                               unsigned __int128>;
  213.  
  214. template <class T>
  215. using is_integral = typename std::conditional<std::is_integral<T>::value ||
  216.                                                   is_signed_int128<T>::value ||
  217.                                                   is_unsigned_int128<T>::value,
  218.                                               std::true_type,
  219.                                               std::false_type>::type;
  220.  
  221. template <class T>
  222. using is_signed_int = typename std::conditional<(is_integral<T>::value &&
  223.                                                  std::is_signed<T>::value) ||
  224.                                                     is_signed_int128<T>::value,
  225.                                                 std::true_type,
  226.                                                 std::false_type>::type;
  227.  
  228. template <class T>
  229. using is_unsigned_int =
  230.     typename std::conditional<(is_integral<T>::value &&
  231.                                std::is_unsigned<T>::value) ||
  232.                                   is_unsigned_int128<T>::value,
  233.                               std::true_type,
  234.                               std::false_type>::type;
  235.  
  236. template <class T>
  237. using to_unsigned = typename std::conditional<
  238.     is_signed_int128<T>::value,
  239.     make_unsigned_int128<T>,
  240.     typename std::conditional<std::is_signed<T>::value,
  241.                               std::make_unsigned<T>,
  242.                               std::common_type<T>>::type>::type;
  243.  
  244. #else
  245.  
  246. template <class T> using is_integral = typename std::is_integral<T>;
  247.  
  248. template <class T>
  249. using is_signed_int =
  250.     typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
  251.                               std::true_type,
  252.                               std::false_type>::type;
  253.  
  254. template <class T>
  255. using is_unsigned_int =
  256.     typename std::conditional<is_integral<T>::value &&
  257.                                   std::is_unsigned<T>::value,
  258.                               std::true_type,
  259.                               std::false_type>::type;
  260.  
  261. template <class T>
  262. using to_unsigned = typename std::conditional<is_signed_int<T>::value,
  263.                                               std::make_unsigned<T>,
  264.                                               std::common_type<T>>::type;
  265.  
  266. #endif
  267.  
  268. template <class T>
  269. using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
  270.  
  271. template <class T>
  272. using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
  273.  
  274. template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
  275.  
  276. }  // namespace internal
  277.  
  278. }  // namespace atcoder
  279.  
  280.  
  281. namespace atcoder {
  282.  
  283. namespace internal {
  284.  
  285. struct modint_base {};
  286. struct static_modint_base : modint_base {};
  287.  
  288. template <class T> using is_modint = std::is_base_of<modint_base, T>;
  289. template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;
  290.  
  291. }  // namespace internal
  292.  
  293. template <int m, std::enable_if_t<(1 <= m)>* = nullptr>
  294. struct static_modint : internal::static_modint_base {
  295.     using mint = static_modint;
  296.  
  297.   public:
  298.     static constexpr int mod() { return m; }
  299.     static mint raw(int v) {
  300.         mint x;
  301.         x._v = v;
  302.         return x;
  303.     }
  304.  
  305.     static_modint() : _v(0) {}
  306.     template <class T, internal::is_signed_int_t<T>* = nullptr>
  307.     static_modint(T v) {
  308.         long long x = (long long)(v % (long long)(umod()));
  309.         if (x < 0) x += umod();
  310.         _v = (unsigned int)(x);
  311.     }
  312.     template <class T, internal::is_unsigned_int_t<T>* = nullptr>
  313.     static_modint(T v) {
  314.         _v = (unsigned int)(v % umod());
  315.     }
  316.  
  317.     unsigned int val() const { return _v; }
  318.  
  319.     mint& operator++() {
  320.         _v++;
  321.         if (_v == umod()) _v = 0;
  322.         return *this;
  323.     }
  324.     mint& operator--() {
  325.         if (_v == 0) _v = umod();
  326.         _v--;
  327.         return *this;
  328.     }
  329.     mint operator++(int) {
  330.         mint result = *this;
  331.         ++*this;
  332.         return result;
  333.     }
  334.     mint operator--(int) {
  335.         mint result = *this;
  336.         --*this;
  337.         return result;
  338.     }
  339.  
  340.     mint& operator+=(const mint& rhs) {
  341.         _v += rhs._v;
  342.         if (_v >= umod()) _v -= umod();
  343.         return *this;
  344.     }
  345.     mint& operator-=(const mint& rhs) {
  346.         _v -= rhs._v;
  347.         if (_v >= umod()) _v += umod();
  348.         return *this;
  349.     }
  350.     mint& operator*=(const mint& rhs) {
  351.         unsigned long long z = _v;
  352.         z *= rhs._v;
  353.         _v = (unsigned int)(z % umod());
  354.         return *this;
  355.     }
  356.     mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
  357.  
  358.     mint operator+() const { return *this; }
  359.     mint operator-() const { return mint() - *this; }
  360.  
  361.     mint pow(long long n) const {
  362.         assert(0 <= n);
  363.         mint x = *this, r = 1;
  364.         while (n) {
  365.             if (n & 1) r *= x;
  366.             x *= x;
  367.             n >>= 1;
  368.         }
  369.         return r;
  370.     }
  371.     mint inv() const {
  372.         if (prime) {
  373.             assert(_v);
  374.             return pow(umod() - 2);
  375.         } else {
  376.             auto eg = internal::inv_gcd(_v, m);
  377.             assert(eg.first == 1);
  378.             return eg.second;
  379.         }
  380.     }
  381.  
  382.     friend mint operator+(const mint& lhs, const mint& rhs) {
  383.         return mint(lhs) += rhs;
  384.     }
  385.     friend mint operator-(const mint& lhs, const mint& rhs) {
  386.         return mint(lhs) -= rhs;
  387.     }
  388.     friend mint operator*(const mint& lhs, const mint& rhs) {
  389.         return mint(lhs) *= rhs;
  390.     }
  391.     friend mint operator/(const mint& lhs, const mint& rhs) {
  392.         return mint(lhs) /= rhs;
  393.     }
  394.     friend bool operator==(const mint& lhs, const mint& rhs) {
  395.         return lhs._v == rhs._v;
  396.     }
  397.     friend bool operator!=(const mint& lhs, const mint& rhs) {
  398.         return lhs._v != rhs._v;
  399.     }
  400.  
  401.   private:
  402.     unsigned int _v;
  403.     static constexpr unsigned int umod() { return m; }
  404.     static constexpr bool prime = internal::is_prime<m>;
  405. };
  406.  
  407. template <int id> struct dynamic_modint : internal::modint_base {
  408.     using mint = dynamic_modint;
  409.  
  410.   public:
  411.     static int mod() { return (int)(bt.umod()); }
  412.     static void set_mod(int m) {
  413.         assert(1 <= m);
  414.         bt = internal::barrett(m);
  415.     }
  416.     static mint raw(int v) {
  417.         mint x;
  418.         x._v = v;
  419.         return x;
  420.     }
  421.  
  422.     dynamic_modint() : _v(0) {}
  423.     template <class T, internal::is_signed_int_t<T>* = nullptr>
  424.     dynamic_modint(T v) {
  425.         long long x = (long long)(v % (long long)(mod()));
  426.         if (x < 0) x += mod();
  427.         _v = (unsigned int)(x);
  428.     }
  429.     template <class T, internal::is_unsigned_int_t<T>* = nullptr>
  430.     dynamic_modint(T v) {
  431.         _v = (unsigned int)(v % mod());
  432.     }
  433.  
  434.     unsigned int val() const { return _v; }
  435.  
  436.     mint& operator++() {
  437.         _v++;
  438.         if (_v == umod()) _v = 0;
  439.         return *this;
  440.     }
  441.     mint& operator--() {
  442.         if (_v == 0) _v = umod();
  443.         _v--;
  444.         return *this;
  445.     }
  446.     mint operator++(int) {
  447.         mint result = *this;
  448.         ++*this;
  449.         return result;
  450.     }
  451.     mint operator--(int) {
  452.         mint result = *this;
  453.         --*this;
  454.         return result;
  455.     }
  456.  
  457.     mint& operator+=(const mint& rhs) {
  458.         _v += rhs._v;
  459.         if (_v >= umod()) _v -= umod();
  460.         return *this;
  461.     }
  462.     mint& operator-=(const mint& rhs) {
  463.         _v += mod() - rhs._v;
  464.         if (_v >= umod()) _v -= umod();
  465.         return *this;
  466.     }
  467.     mint& operator*=(const mint& rhs) {
  468.         _v = bt.mul(_v, rhs._v);
  469.         return *this;
  470.     }
  471.     mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }
  472.  
  473.     mint operator+() const { return *this; }
  474.     mint operator-() const { return mint() - *this; }
  475.  
  476.     mint pow(long long n) const {
  477.         assert(0 <= n);
  478.         mint x = *this, r = 1;
  479.         while (n) {
  480.             if (n & 1) r *= x;
  481.             x *= x;
  482.             n >>= 1;
  483.         }
  484.         return r;
  485.     }
  486.     mint inv() const {
  487.         auto eg = internal::inv_gcd(_v, mod());
  488.         assert(eg.first == 1);
  489.         return eg.second;
  490.     }
  491.  
  492.     friend mint operator+(const mint& lhs, const mint& rhs) {
  493.         return mint(lhs) += rhs;
  494.     }
  495.     friend mint operator-(const mint& lhs, const mint& rhs) {
  496.         return mint(lhs) -= rhs;
  497.     }
  498.     friend mint operator*(const mint& lhs, const mint& rhs) {
  499.         return mint(lhs) *= rhs;
  500.     }
  501.     friend mint operator/(const mint& lhs, const mint& rhs) {
  502.         return mint(lhs) /= rhs;
  503.     }
  504.     friend bool operator==(const mint& lhs, const mint& rhs) {
  505.         return lhs._v == rhs._v;
  506.     }
  507.     friend bool operator!=(const mint& lhs, const mint& rhs) {
  508.         return lhs._v != rhs._v;
  509.     }
  510.  
  511.   private:
  512.     unsigned int _v;
  513.     static internal::barrett bt;
  514.     static unsigned int umod() { return bt.umod(); }
  515. };
  516. template <int id> internal::barrett dynamic_modint<id>::bt(998244353);
  517.  
  518. using modint998244353 = static_modint<998244353>;
  519. using modint1000000007 = static_modint<1000000007>;
  520. using modint = dynamic_modint<-1>;
  521.  
  522. namespace internal {
  523.  
  524. template <class T>
  525. using is_static_modint = std::is_base_of<internal::static_modint_base, T>;
  526.  
  527. template <class T>
  528. using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;
  529.  
  530. template <class> struct is_dynamic_modint : public std::false_type {};
  531. template <int id>
  532. struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};
  533.  
  534. template <class T>
  535. using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;
  536.  
  537. }  // namespace internal
  538.  
  539. }  // namespace atcoder
  540.  
  541.  
  542. #include <algorithm>
  543. #include <cassert>
  544. #include <vector>
  545.  
  546.  
  547. #include <algorithm>
  548. #include <utility>
  549. #include <vector>
  550.  
  551.  
  552. #include <algorithm>
  553. #include <utility>
  554. #include <vector>
  555.  
  556. namespace atcoder {
  557. namespace internal {
  558.  
  559. template <class E> struct csr {
  560.     std::vector<int> start;
  561.     std::vector<E> elist;
  562.     explicit csr(int n, const std::vector<std::pair<int, E>>& edges)
  563.         : start(n + 1), elist(edges.size()) {
  564.         for (auto e : edges) {
  565.             start[e.first + 1]++;
  566.         }
  567.         for (int i = 1; i <= n; i++) {
  568.             start[i] += start[i - 1];
  569.         }
  570.         auto counter = start;
  571.         for (auto e : edges) {
  572.             elist[counter[e.first]++] = e.second;
  573.         }
  574.     }
  575. };
  576.  
  577. }  // namespace internal
  578.  
  579. }  // namespace atcoder
  580.  
  581.  
  582. namespace atcoder {
  583. namespace internal {
  584.  
  585. struct scc_graph {
  586.   public:
  587.     explicit scc_graph(int n) : _n(n) {}
  588.  
  589.     int num_vertices() { return _n; }
  590.  
  591.     void add_edge(int from, int to) { edges.push_back({from, {to}}); }
  592.  
  593.     std::pair<int, std::vector<int>> scc_ids() {
  594.         auto g = csr<edge>(_n, edges);
  595.         int now_ord = 0, group_num = 0;
  596.         std::vector<int> visited, low(_n), ord(_n, -1), ids(_n);
  597.         visited.reserve(_n);
  598.         auto dfs = [&](auto self, int v) -> void {
  599.             low[v] = ord[v] = now_ord++;
  600.             visited.push_back(v);
  601.             for (int i = g.start[v]; i < g.start[v + 1]; i++) {
  602.                 auto to = g.elist[i].to;
  603.                 if (ord[to] == -1) {
  604.                     self(self, to);
  605.                     low[v] = std::min(low[v], low[to]);
  606.                 } else {
  607.                     low[v] = std::min(low[v], ord[to]);
  608.                 }
  609.             }
  610.             if (low[v] == ord[v]) {
  611.                 while (true) {
  612.                     int u = visited.back();
  613.                     visited.pop_back();
  614.                     ord[u] = _n;
  615.                     ids[u] = group_num;
  616.                     if (u == v) break;
  617.                 }
  618.                 group_num++;
  619.             }
  620.         };
  621.         for (int i = 0; i < _n; i++) {
  622.             if (ord[i] == -1) dfs(dfs, i);
  623.         }
  624.         for (auto& x : ids) {
  625.             x = group_num - 1 - x;
  626.         }
  627.         return {group_num, ids};
  628.     }
  629.  
  630.     std::vector<std::vector<int>> scc() {
  631.         auto ids = scc_ids();
  632.         int group_num = ids.first;
  633.         std::vector<int> counts(group_num);
  634.         for (auto x : ids.second) counts[x]++;
  635.         std::vector<std::vector<int>> groups(ids.first);
  636.         for (int i = 0; i < group_num; i++) {
  637.             groups[i].reserve(counts[i]);
  638.         }
  639.         for (int i = 0; i < _n; i++) {
  640.             groups[ids.second[i]].push_back(i);
  641.         }
  642.         return groups;
  643.     }
  644.  
  645.   private:
  646.     int _n;
  647.     struct edge {
  648.         int to;
  649.     };
  650.     std::vector<std::pair<int, edge>> edges;
  651. };
  652.  
  653. }  // namespace internal
  654.  
  655. }  // namespace atcoder
  656.  
  657.  
  658. namespace atcoder {
  659.  
  660. struct scc_graph {
  661.   public:
  662.     scc_graph() : internal(0) {}
  663.     explicit scc_graph(int n) : internal(n) {}
  664.  
  665.     void add_edge(int from, int to) {
  666.         int n = internal.num_vertices();
  667.         assert(0 <= from && from < n);
  668.         assert(0 <= to && to < n);
  669.         internal.add_edge(from, to);
  670.     }
  671.  
  672.     std::vector<std::vector<int>> scc() { return internal.scc(); }
  673.  
  674.   private:
  675.     internal::scc_graph internal;
  676. };
  677.  
  678. }  // namespace atcoder
  679.  
  680. //using mint = atcoder::modint998244353;
  681. //using mint = atcoder::modint1000000007;
  682. using mint = atcoder::dynamic_modint<-2>;
  683. using vm = std::vector<mint>;
  684. std::ostream& operator << (std::ostream& out, const mint& rhs) {
  685.         return out<<rhs.val();
  686.     }
  687. #ifdef ARYANC403
  688.     #include <header.h>
  689. #else
  690.     #pragma GCC optimize ("Ofast")
  691.     #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
  692.     // #pragma GCC target ("sse,sse2,mmx")
  693.     #pragma GCC optimize ("-ffloat-store")
  694.     #include <bits/stdc++.h>
  695.     #include <ext/pb_ds/assoc_container.hpp>
  696.     #include <ext/pb_ds/tree_policy.hpp>
  697.     #define dbg(args...) 42;
  698.     // #define endl "\n"
  699. #endif
  700.  
  701. // y_combinator from @neal template https://c...content-available-to-author-only...s.com/contest/1553/submission/123849801
  702. // http://w...content-available-to-author-only...d.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html
  703. template<class Fun> class y_combinator_result {
  704.     Fun fun_;
  705. public:
  706.     template<class T> explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}
  707.     template<class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); }
  708. };
  709. template<class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }
  710.  
  711. using namespace std;
  712. #define fo(i,n)   for(i=0;i<(n);++i)
  713. #define repA(i,j,n)   for(i=(j);i<=(n);++i)
  714. #define repD(i,j,n)   for(i=(j);i>=(n);--i)
  715. #define all(x) begin(x), end(x)
  716. #define sz(x) ((lli)(x).size())
  717. #define eb emplace_back
  718. #define X first
  719. #define Y second
  720.  
  721. using lli = long long int;
  722. using mytype = long double;
  723. using ii = pair<lli,lli>;
  724. using vii = vector<ii>;
  725. using vi = vector<lli>;
  726.  
  727. template <class T>
  728. using ordered_set =  __gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
  729. // X.find_by_order(k) return kth element. 0 indexed.
  730. // X.order_of_key(k) returns count of elements strictly less than k.
  731.  
  732. // namespace Re = std::ranges;
  733. // namespace Ve = std::ranges::views;
  734.  
  735. const auto start_time = std::chrono::high_resolution_clock::now();
  736. void aryanc403()
  737. {
  738. auto end_time = std::chrono::high_resolution_clock::now();
  739. std::chrono::duration<double> diff = end_time-start_time;
  740.     cerr<<"Time Taken : "<<diff.count()<<"\n";
  741. }
  742.  
  743. const lli INF = 0xFFFFFFFFFFFFFFFLL;
  744. const lli SEED=chrono::steady_clock::now().time_since_epoch().count();
  745. mt19937_64 rng(SEED);
  746. inline lli rnd(lli l=0,lli r=INF)
  747. {return uniform_int_distribution<lli>(l,r)(rng);}
  748.  
  749. class CMP
  750. {public:
  751. bool operator()(ii a , ii b) //For min priority_queue .
  752. {    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};
  753.  
  754. void add( map<lli,lli> &m, lli x,lli cnt=1)
  755. {
  756.     auto jt=m.find(x);
  757.     if(jt==m.end())         m.insert({x,cnt});
  758.     else                    jt->Y+=cnt;
  759. }
  760.  
  761. void del( map<lli,lli> &m, lli x,lli cnt=1)
  762. {
  763.     auto jt=m.find(x);
  764.     if(jt->Y<=cnt)            m.erase(jt);
  765.     else                      jt->Y-=cnt;
  766. }
  767.  
  768. bool cmp(const ii &a,const ii &b)
  769. {
  770.     return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
  771. }
  772.  
  773. // Ref - https://w...content-available-to-author-only...f.com/viewsolution/41909444 Line 827 - 850.
  774. const int maxnCr=2e6+5;
  775. array<mint,maxnCr+1> fac,inv;
  776.  
  777. mint nCr(lli n,lli r)
  778. {
  779.     if(n<0||r<0||r>n)
  780.         return 0;
  781.     return fac[n]*inv[r]*inv[n-r];
  782. }
  783.  
  784. void pre(lli n)
  785. {
  786.     fac[0]=1;
  787.     for(int i=1;i<=n;++i)
  788.         fac[i]=i*fac[i-1];
  789.     inv[n]=fac[n].pow(mint(-2).val());
  790.     for(int i=n;i>0;--i)
  791.         inv[i-1]=i*inv[i];
  792.     assert(inv[0]==mint(1));
  793. }
  794.  
  795. mint brute(const lli n){
  796.     vii ord;
  797.     for(lli i=0;i<n;i++)
  798.         for(lli j=0;j<i;j++)
  799.             ord.eb(ii{i,j});
  800.     mint ans = 0;
  801.     vi type(sz(ord));
  802.  
  803.     auto run=[&]()->void{
  804.         atcoder::scc_graph g(n);
  805.         vector<bool> pos(n,true);
  806.         for(lli idx=0;idx<sz(ord);idx++){
  807.             const lli u=ord[idx].X,v=ord[idx].Y;
  808.             if(type[idx]==0)
  809.                 continue;
  810.             if(type[idx]==1){
  811.                 g.add_edge(u,v);
  812.                 pos[v]=false;
  813.                 continue;
  814.             }
  815.             g.add_edge(v,u);
  816.             pos[u]=false;
  817.         }
  818.         if(sz(g.scc())!=n)
  819.             return;
  820.         for(auto x:pos)
  821.             if(x)
  822.                 ans++;
  823.     };
  824.  
  825.     y_combinator([&](const auto &self,const lli idx)->void{
  826.         if(idx==sz(ord)){
  827.             run();
  828.             return;
  829.         }
  830.         type[idx]=0;
  831.         self(idx+1);
  832.         type[idx]=1;
  833.         self(idx+1);
  834.         type[idx]=2;
  835.         self(idx+1);
  836.     })(0);
  837.     return ans;
  838. }
  839.  
  840. mint solve(const lli N){
  841.     vm dp(N+1);
  842.  
  843.     auto get=[&](const lli n,const lli k)->mint{
  844.         return dp[n-k]*(mint(2).pow(k*(n-k)));
  845.     };
  846.  
  847.     dp[0]=1;
  848.     for(lli n=1;n<=N;n++){
  849.         for(lli k=1,sgn=1;k<=n;k++,sgn*=-1)
  850.             dp[n]+=sgn*nCr(n,k)*get(n,k);
  851.         // dbg(n,dp[n]);
  852.     }
  853.  
  854.     mint ans = N*(mint(2).pow(N-1))*dp[N-1];
  855.     return ans;
  856. }
  857.  
  858. void stress(const lli N){
  859.     pre(2*N);
  860.     mint::set_mod(998244353);
  861.     for(lli n=1;n<=N;n++){
  862.         dbg(n,brute(n),solve(n));
  863.         assert(brute(n)==solve(n));
  864.         cerr<<"verified"<<n<<endl;
  865.     }
  866. }
  867.  
  868. int main(void) {
  869.     ios_base::sync_with_stdio(false);cin.tie(NULL);
  870.     // freopen("txt.in", "r", stdin);
  871.     // freopen("txt.out", "w", stdout);
  872. // cout<<std::fixed<<std::setprecision(35);
  873. // Ve::iota(1, 6) | Ve::transform([](int x) { return x * 2; }) | Ve::reverse | Ve::take(3)
  874. // stress(7);
  875. // return 0;
  876. lli T=1;
  877. cin>>T;
  878. while(T--)
  879. {
  880.     lli n,p;
  881.     cin>>n>>p;
  882.     mint::set_mod(p);
  883.     pre(2*n);
  884.  
  885.     cout<<solve(n)<<endl;
  886.  
  887. }   aryanc403();
  888.     return 0;
  889. }
Runtime error #stdin #stdout 0.08s 18964KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pM5ibB
language:
C++14 (gcc 8.3)
created:
236 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!