API tools faq
paste
Advertisement
BaoJIaoPisu

Untitled

BaoJIaoPisu
Jan 4th, 2022
97
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 19.01 KB | None | 0 0
raw download clone embed print report
  1. /**
  2.  *    author:  tourist
  3.  *    created: 22.07.2021 19:02:12      
  4. **/
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. template <typename A, typename B>
  10. string to_string(pair<A, B> p);
  11.  
  12. template <typename A, typename B, typename C>
  13. string to_string(tuple<A, B, C> p);
  14.  
  15. template <typename A, typename B, typename C, typename D>
  16. string to_string(tuple<A, B, C, D> p);
  17.  
  18. string to_string(const string& s) {
  19.   return '"' + s + '"';
  20. }
  21.  
  22. string to_string(const char* s) {
  23.   return to_string((string) s);
  24. }
  25.  
  26. string to_string(bool b) {
  27.   return (b ? "true" : "false");
  28. }
  29.  
  30. string to_string(vector<bool> v) {
  31.   bool first = true;
  32.   string res = "{";
  33.   for (int i = 0; i < static_cast<int>(v.size()); i++) {
  34.     if (!first) {
  35.       res += ", ";
  36.     }
  37.     first = false;
  38.     res += to_string(v[i]);
  39.   }
  40.   res += "}";
  41.   return res;
  42. }
  43.  
  44. template <size_t N>
  45. string to_string(bitset<N> v) {
  46.   string res = "";
  47.   for (size_t i = 0; i < N; i++) {
  48.     res += static_cast<char>('0' + v[i]);
  49.   }
  50.   return res;
  51. }
  52.  
  53. template <typename A>
  54. string to_string(A v) {
  55.   bool first = true;
  56.   string res = "{";
  57.   for (const auto &x : v) {
  58.     if (!first) {
  59.       res += ", ";
  60.     }
  61.     first = false;
  62.     res += to_string(x);
  63.   }
  64.   res += "}";
  65.   return res;
  66. }
  67.  
  68. template <typename A, typename B>
  69. string to_string(pair<A, B> p) {
  70.   return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
  71. }
  72.  
  73. template <typename A, typename B, typename C>
  74. string to_string(tuple<A, B, C> p) {
  75.   return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
  76. }
  77.  
  78. template <typename A, typename B, typename C, typename D>
  79. string to_string(tuple<A, B, C, D> p) {
  80.   return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
  81. }
  82.  
  83. void debug_out() { cerr << endl; }
  84.  
  85. template <typename Head, typename... Tail>
  86. void debug_out(Head H, Tail... T) {
  87.   cerr << " " << to_string(H);
  88.   debug_out(T...);
  89. }
  90.  
  91. #ifdef LOCAL
  92. #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  93. #else
  94. #define debug(...) 42
  95. #endif
  96.  
  97. template <typename T>
  98. T inverse(T a, T m) {
  99.   T u = 0, v = 1;
  100.   while (a != 0) {
  101.     T t = m / a;
  102.     m -= t * a; swap(a, m);
  103.     u -= t * v; swap(u, v);
  104.   }
  105.   assert(m == 1);
  106.   return u;
  107. }
  108.  
  109. template <typename T>
  110. class Modular {
  111.  public:
  112.   using Type = typename decay<decltype(T::value)>::type;
  113.  
  114.   constexpr Modular() : value() {}
  115.   template <typename U>
  116.   Modular(const U& x) {
  117.     value = normalize(x);
  118.   }
  119.  
  120.   template <typename U>
  121.   static Type normalize(const U& x) {
  122.     Type v;
  123.     if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
  124.     else v = static_cast<Type>(x % mod());
  125.     if (v < 0) v += mod();
  126.     return v;
  127.   }
  128.  
  129.   const Type& operator()() const { return value; }
  130.   template <typename U>
  131.   explicit operator U() const { return static_cast<U>(value); }
  132.   constexpr static Type mod() { return T::value; }
  133.  
  134.   Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
  135.   Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  136.   template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
  137.   template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
  138.   Modular& operator++() { return *this += 1; }
  139.   Modular& operator--() { return *this -= 1; }
  140.   Modular operator++(int) { Modular result(*this); *this += 1; return result; }
  141.   Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
  142.   Modular operator-() const { return Modular(-value); }
  143.  
  144.   template <typename U = T>
  145.   typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
  146. #ifdef _WIN32
  147.     uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
  148.     uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
  149.     asm(
  150.       "divl %4; \n\t"
  151.       : "=a" (d), "=d" (m)
  152.       : "d" (xh), "a" (xl), "r" (mod())
  153.     );
  154.     value = m;
  155. #else
  156.     value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
  157. #endif
  158.     return *this;
  159.   }
  160.   template <typename U = T>
  161.   typename enable_if<is_same<typename Modular<U>::Type, long long>::value, Modular>::type& operator*=(const Modular& rhs) {
  162.     long long q = static_cast<long long>(static_cast<long double>(value) * rhs.value / mod());
  163.     value = normalize(value * rhs.value - q * mod());
  164.     return *this;
  165.   }
  166.   template <typename U = T>
  167.   typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
  168.     value = normalize(value * rhs.value);
  169.     return *this;
  170.   }
  171.  
  172.   Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }
  173.  
  174.   friend const Type& abs(const Modular& x) { return x.value; }
  175.  
  176.   template <typename U>
  177.   friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);
  178.  
  179.   template <typename U>
  180.   friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);
  181.  
  182.   template <typename V, typename U>
  183.   friend V& operator>>(V& stream, Modular<U>& number);
  184.  
  185.  private:
  186.   Type value;
  187. };
  188.  
  189. template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
  190. template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
  191. template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }
  192.  
  193. template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
  194. template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
  195. template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
  196.  
  197. template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }
  198.  
  199. template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
  200. template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
  201. template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
  202.  
  203. template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
  204. template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
  205. template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
  206.  
  207. template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
  208. template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
  209. template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
  210.  
  211. template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
  212. template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
  213. template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
  214.  
  215. template<typename T, typename U>
  216. Modular<T> power(const Modular<T>& a, const U& b) {
  217.   assert(b >= 0);
  218.   Modular<T> x = a, res = 1;
  219.   U p = b;
  220.   while (p > 0) {
  221.     if (p & 1) res *= x;
  222.     x *= x;
  223.     p >>= 1;
  224.   }
  225.   return res;
  226. }
  227.  
  228. template <typename T>
  229. bool IsZero(const Modular<T>& number) {
  230.   return number() == 0;
  231. }
  232.  
  233. template <typename T>
  234. string to_string(const Modular<T>& number) {
  235.   return to_string(number());
  236. }
  237.  
  238. // U == std::ostream? but done this way because of fastoutput
  239. template <typename U, typename T>
  240. U& operator<<(U& stream, const Modular<T>& number) {
  241.   return stream << number();
  242. }
  243.  
  244. // U == std::istream? but done this way because of fastinput
  245. template <typename U, typename T>
  246. U& operator>>(U& stream, Modular<T>& number) {
  247.   typename common_type<typename Modular<T>::Type, long long>::type x;
  248.   stream >> x;
  249.   number.value = Modular<T>::normalize(x);
  250.   return stream;
  251. }
  252.  
  253. /*
  254. using ModType = int;
  255.  
  256. struct VarMod { static ModType value; };
  257. ModType VarMod::value;
  258. ModType& md = VarMod::value;
  259. using Mint = Modular<VarMod>;
  260. */
  261.  
  262. constexpr int md = 998244353;
  263. using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;
  264.  
  265. vector<Mint> fact(1, 1);
  266. vector<Mint> inv_fact(1, 1);
  267.  
  268. Mint C(int n, int k) {
  269.   if (k < 0 || k > n) {
  270.     return 0;
  271.   }
  272.   while ((int) fact.size() < n + 1) {
  273.     fact.push_back(fact.back() * (int) fact.size());
  274.     inv_fact.push_back(1 / fact.back());
  275.   }
  276.   return fact[n] * inv_fact[k] * inv_fact[n - k];
  277. }
  278.  
  279. template <typename T>
  280. class NTT {
  281.  public:
  282.   using Type = typename decay<decltype(T::value)>::type;
  283.  
  284.   static Type md;
  285.   static Modular<T> root;
  286.   static int base;
  287.   static int max_base;
  288.   static vector<Modular<T>> roots;
  289.   static vector<int> rev;
  290.  
  291.   static void clear() {
  292.     root = 0;
  293.     base = 0;
  294.     max_base = 0;
  295.     roots.clear();
  296.     rev.clear();
  297.   }
  298.  
  299.   static void init() {
  300.     md = T::value;
  301.     assert(md >= 3 && md % 2 == 1);
  302.     auto tmp = md - 1;
  303.     max_base = 0;
  304.     while (tmp % 2 == 0) {
  305.       tmp /= 2;
  306.       max_base++;
  307.     }
  308.     root = 2;
  309.     while (power(root, (md - 1) >> 1) == 1) {
  310.       root++;
  311.     }
  312.     assert(power(root, md - 1) == 1);
  313.     root = power(root, (md - 1) >> max_base);
  314.     base = 1;
  315.     rev = {0, 1};
  316.     roots = {0, 1};
  317.   }
  318.  
  319.   static void ensure_base(int nbase) {
  320.     if (md != T::value) {
  321.       clear();
  322.     }
  323.     if (roots.empty()) {
  324.       init();
  325.     }
  326.     if (nbase <= base) {
  327.       return;
  328.     }
  329.     assert(nbase <= max_base);
  330.     rev.resize(1 << nbase);
  331.     for (int i = 0; i < (1 << nbase); i++) {
  332.       rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (nbase - 1));
  333.     }
  334.     roots.resize(1 << nbase);
  335.     while (base < nbase) {
  336.       Modular<T> z = power(root, 1 << (max_base - 1 - base));
  337.       for (int i = 1 << (base - 1); i < (1 << base); i++) {
  338.         roots[i << 1] = roots[i];
  339.         roots[(i << 1) + 1] = roots[i] * z;
  340.       }
  341.       base++;
  342.     }
  343.   }
  344.  
  345.   static void fft(vector<Modular<T>> &a) {
  346.     int n = (int) a.size();
  347.     assert((n & (n - 1)) == 0);
  348.     int zeros = __builtin_ctz(n);
  349.     ensure_base(zeros);
  350.     int shift = base - zeros;
  351.     for (int i = 0; i < n; i++) {
  352.       if (i < (rev[i] >> shift)) {
  353.         swap(a[i], a[rev[i] >> shift]);
  354.       }
  355.     }
  356.     for (int k = 1; k < n; k <<= 1) {
  357.       for (int i = 0; i < n; i += 2 * k) {
  358.         for (int j = 0; j < k; j++) {
  359.           Modular<T> x = a[i + j];
  360.           Modular<T> y = a[i + j + k] * roots[j + k];
  361.           a[i + j] = x + y;
  362.           a[i + j + k] = x - y;
  363.         }
  364.       }
  365.     }
  366.   }
  367.  
  368.   static vector<Modular<T>> multiply(vector<Modular<T>> a, vector<Modular<T>> b) {
  369.     if (a.empty() || b.empty()) {
  370.       return {};
  371.     }
  372.     int eq = (a == b);
  373.     int need = (int) a.size() + (int) b.size() - 1;
  374.     int nbase = 0;
  375.     while ((1 << nbase) < need) nbase++;
  376.     ensure_base(nbase);
  377.     int sz = 1 << nbase;
  378.     a.resize(sz);
  379.     b.resize(sz);
  380.     fft(a);
  381.     if (eq) b = a; else fft(b);
  382.     Modular<T> inv_sz = 1 / static_cast<Modular<T>>(sz);
  383.     for (int i = 0; i < sz; i++) {
  384.       a[i] *= b[i] * inv_sz;
  385.     }
  386.     reverse(a.begin() + 1, a.end());
  387.     fft(a);
  388.     a.resize(need);
  389.     return a;
  390.   }
  391. };
  392.  
  393. template <typename T> typename NTT<T>::Type NTT<T>::md;
  394. template <typename T> Modular<T> NTT<T>::root;
  395. template <typename T> int NTT<T>::base;
  396. template <typename T> int NTT<T>::max_base;
  397. template <typename T> vector<Modular<T>> NTT<T>::roots;
  398. template <typename T> vector<int> NTT<T>::rev;
  399.  
  400. template <typename T>
  401. vector<Modular<T>> inverse(const vector<Modular<T>>& a) {
  402.   assert(!a.empty());
  403.   int n = (int) a.size();
  404.   vector<Modular<T>> b = {1 / a[0]};
  405.   while ((int) b.size() < n) {
  406.     vector<Modular<T>> x(a.begin(), a.begin() + min(a.size(), b.size() << 1));
  407.     x.resize(b.size() << 1);
  408.     b.resize(b.size() << 1);
  409.     vector<Modular<T>> c = b;
  410.     NTT<T>::fft(c);
  411.     NTT<T>::fft(x);
  412.     Modular<T> inv = 1 / static_cast<Modular<T>>((int) x.size());
  413.     for (int i = 0; i < (int) x.size(); i++) {
  414.       x[i] *= c[i] * inv;
  415.     }
  416.     reverse(x.begin() + 1, x.end());
  417.     NTT<T>::fft(x);
  418.     rotate(x.begin(), x.begin() + (x.size() >> 1), x.end());
  419.     fill(x.begin() + (x.size() >> 1), x.end(), 0);
  420.     NTT<T>::fft(x);
  421.     for (int i = 0; i < (int) x.size(); i++) {
  422.       x[i] *= c[i] * inv;
  423.     }
  424.     reverse(x.begin() + 1, x.end());
  425.     NTT<T>::fft(x);
  426.     for (int i = 0; i < ((int) x.size() >> 1); i++) {
  427.       b[i + ((int) x.size() >> 1)] = -x[i];
  428.     }
  429.   }
  430.   b.resize(n);
  431.   return b;
  432. }
  433.  
  434. template <typename T>
  435. vector<Modular<T>> inverse_old(vector<Modular<T>> a) {
  436.   assert(!a.empty());
  437.   int n = (int) a.size();
  438.   if (n == 1) {
  439.     return {1 / a[0]};
  440.   }
  441.   int m = (n + 1) >> 1;
  442.   vector<Modular<T>> b = inverse(vector<Modular<T>>(a.begin(), a.begin() + m));
  443.   int need = n << 1;
  444.   int nbase = 0;
  445.   while ((1 << nbase) < need) {
  446.     ++nbase;
  447.   }
  448.   NTT<T>::ensure_base(nbase);
  449.   int size = 1 << nbase;
  450.   a.resize(size);
  451.   b.resize(size);
  452.   NTT<T>::fft(a);
  453.   NTT<T>::fft(b);
  454.   Modular<T> inv = 1 / static_cast<Modular<T>>(size);
  455.   for (int i = 0; i < size; ++i) {
  456.     a[i] = (2 - a[i] * b[i]) * b[i] * inv;
  457.   }
  458.   reverse(a.begin() + 1, a.end());
  459.   NTT<T>::fft(a);
  460.   a.resize(n);
  461.   return a;
  462. }
  463.  
  464. template <typename T>
  465. vector<Modular<T>> operator*(const vector<Modular<T>>& a, const vector<Modular<T>>& b) {
  466.   if (a.empty() || b.empty()) {
  467.     return {};
  468.   }
  469.   if (min(a.size(), b.size()) < 150) {
  470.     vector<Modular<T>> c(a.size() + b.size() - 1, 0);
  471.     for (int i = 0; i < (int) a.size(); i++) {
  472.       for (int j = 0; j < (int) b.size(); j++) {
  473.         c[i + j] += a[i] * b[j];
  474.       }
  475.     }
  476.     return c;
  477.   }
  478.   return NTT<T>::multiply(a, b);
  479. }
  480.  
  481. template <typename T>
  482. vector<Modular<T>>& operator*=(vector<Modular<T>>& a, const vector<Modular<T>>& b) {
  483.   return a = a * b;
  484. }
  485.  
  486. template <typename T>
  487. vector<T>& operator+=(vector<T>& a, const vector<T>& b) {
  488.   if (a.size() < b.size()) {
  489.     a.resize(b.size());
  490.   }
  491.   for (int i = 0; i < (int) b.size(); i++) {
  492.     a[i] += b[i];
  493.   }
  494.   return a;
  495. }
  496.  
  497. template <typename T>
  498. vector<T> operator+(const vector<T>& a, const vector<T>& b) {
  499.   vector<T> c = a;
  500.   return c += b;
  501. }
  502.  
  503. template <typename T>
  504. vector<T>& operator-=(vector<T>& a, const vector<T>& b) {
  505.   if (a.size() < b.size()) {
  506.     a.resize(b.size());
  507.   }
  508.   for (int i = 0; i < (int) b.size(); i++) {
  509.     a[i] -= b[i];
  510.   }
  511.   return a;
  512. }
  513.  
  514. template <typename T>
  515. vector<T> operator-(const vector<T>& a, const vector<T>& b) {
  516.   vector<T> c = a;
  517.   return c -= b;
  518. }
  519.  
  520. template <typename T>
  521. vector<T> operator-(const vector<T>& a) {
  522.   vector<T> c = a;
  523.   for (int i = 0; i < (int) c.size(); i++) {
  524.     c[i] = -c[i];
  525.   }
  526.   return c;
  527. }
  528.  
  529. template <typename T>
  530. vector<T> operator*(const vector<T>& a, const vector<T>& b) {
  531.   if (a.empty() || b.empty()) {
  532.     return {};
  533.   }
  534.   vector<T> c(a.size() + b.size() - 1, 0);
  535.   for (int i = 0; i < (int) a.size(); i++) {
  536.     for (int j = 0; j < (int) b.size(); j++) {
  537.       c[i + j] += a[i] * b[j];
  538.     }
  539.   }
  540.   return c;
  541. }
  542.  
  543. template <typename T>
  544. vector<T>& operator*=(vector<T>& a, const vector<T>& b) {
  545.   return a = a * b;
  546. }
  547.  
  548. template <typename T>
  549. vector<T> inverse(const vector<T>& a) {
  550.   assert(!a.empty());
  551.   int n = (int) a.size();
  552.   vector<T> b = {1 / a[0]};
  553.   while ((int) b.size() < n) {
  554.     vector<T> a_cut(a.begin(), a.begin() + min(a.size(), b.size() << 1));
  555.     vector<T> x = b * b * a_cut;
  556.     b.resize(b.size() << 1);
  557.     for (int i = (int) b.size() >> 1; i < (int) min(x.size(), b.size()); i++) {
  558.       b[i] = -x[i];
  559.     }
  560.   }
  561.   b.resize(n);
  562.   return b;
  563. }
  564.  
  565. template <typename T>
  566. vector<T>& operator/=(vector<T>& a, const vector<T>& b) {
  567.   int n = (int) a.size();
  568.   int m = (int) b.size();
  569.   if (n < m) {
  570.     a.clear();
  571.   } else {
  572.     vector<T> d = b;
  573.     reverse(a.begin(), a.end());
  574.     reverse(d.begin(), d.end());
  575.     d.resize(n - m + 1);
  576.     a *= inverse(d);
  577.     a.erase(a.begin() + n - m + 1, a.end());
  578.     reverse(a.begin(), a.end());
  579.   }
  580.   return a;
  581. }
  582.  
  583. template <typename T>
  584. vector<T> operator/(const vector<T>& a, const vector<T>& b) {
  585.   vector<T> c = a;
  586.   return c /= b;
  587. }
  588.  
  589. template <typename T>
  590. vector<T>& operator%=(vector<T>& a, const vector<T>& b) {
  591.   int n = (int) a.size();
  592.   int m = (int) b.size();
  593.   if (n >= m) {
  594.     vector<T> c = (a / b) * b;
  595.     a.resize(m - 1);
  596.     for (int i = 0; i < m - 1; i++) {
  597.       a[i] -= c[i];
  598.     }
  599.   }
  600.   return a;
  601. }
  602.  
  603. template <typename T>
  604. vector<T> operator%(const vector<T>& a, const vector<T>& b) {
  605.   vector<T> c = a;
  606.   return c %= b;
  607. }
  608.  
  609. template <typename T, typename U>
  610. vector<T> power(const vector<T>& a, const U& b, const vector<T>& c) {
  611.   assert(b >= 0);
  612.   vector<U> binary;
  613.   U bb = b;
  614.   while (bb > 0) {
  615.     binary.push_back(bb & 1);
  616.     bb >>= 1;
  617.   }
  618.   vector<T> res = vector<T>{1} % c;
  619.   for (int j = (int) binary.size() - 1; j >= 0; j--) {
  620.     res = res * res % c;
  621.     if (binary[j] == 1) {
  622.       res = res * a % c;
  623.     }
  624.   }
  625.   return res;
  626. }
  627.  
  628.  
  629. int main() {
  630.   ios::sync_with_stdio(false);
  631.   cin.tie(0);
  632.   int n;
  633.   cin >> n;
  634.   vector<int> init(n);
  635.   for (int i = 0; i < n; i++) {
  636.     cin >> init[i];
  637.   }
  638.   vector<int> a;
  639.   int beg = 0;
  640.   while (beg < n) {
  641.     int len = init[beg];
  642.     if (beg + len > n) {
  643.       cout << 0 << '\n';
  644.       return 0;
  645.     }
  646.     for (int i = beg; i < beg + len; i++) {
  647.       if (init[i] != len) {
  648.         cout << 0 << '\n';
  649.         return 0;
  650.       }
  651.     }
  652.     a.push_back(len);
  653.     beg += len;
  654.   }
  655. //  debug(a);
  656.   // 0 to 0, 0 to 1, 1 to 0, 1 to 1
  657.   function<vector<vector<Mint>>(int, int)> Solve = [&](int L, int R) {
  658.     if (R - L == 1) {
  659.       vector<vector<Mint>> ret(4);
  660.       if (a[L] > 1) {
  661.         ret[0] = vector<Mint>{1};
  662.         ret[1] = vector<Mint>{0, 2};
  663.         ret[2] = vector<Mint>{1};
  664.         ret[3] = vector<Mint>{0, 2};
  665.       } else {
  666.         ret[0] = vector<Mint>{1};
  667.         ret[1] = vector<Mint>{0, 2};
  668.         ret[2] = vector<Mint>{1};
  669.         ret[3] = vector<Mint>{0, 1};
  670.       }
  671.       return ret;
  672.     }
  673.     int M = (L + R) >> 1;
  674.     auto x = Solve(L, M);
  675.     auto y = Solve(M, R);
  676.     vector<vector<Mint>> ret(4);
  677.     ret[0] = x[0] * y[0] + x[1] * y[2];
  678.     ret[1] = x[0] * y[1] + x[1] * y[3];
  679.     ret[2] = x[2] * y[0] + x[3] * y[2];
  680.     ret[3] = x[3] * y[3] + x[2] * y[1];
  681.     return ret;
  682.   };
  683.   auto ret = Solve(0, (int) a.size());
  684.   auto p1 = ret[3];
  685.   C(n, 0);
  686.   Mint ans = 0;
  687.   for (int k = 1; k < (int) p1.size(); k++) {
  688.     ans += p1[k] * fact[k] * (k % 2 == (int) p1.size() % 2 ? -1 : 1);
  689.   }
  690.   cout << ans << '\n';
  691.   return 0;
  692. }
  693.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!