Harbour.Space Scholarship Contest 2021-2022 (Div. 1 + Div. 2) Editorial
Difference between en1 and en2, changed 21,493 character(s)
Hope you all enjoyed the problemset! Editorials to problems H and I are not ready yet, we will add them as soon as possible.

[problem:1553A]↵

<spoiler summary="Solution">↵
[tutorial:1553A]↵
</spoiler>↵


<spoiler summary="Solution Code">↵
...↵
</spoiler>↵

[problem:1553B]↵

<spoiler summary="Solution">↵
[tutorial:1553B]↵
</spoiler>↵


<spoiler summary="Solution Code">↵
...↵
</spoiler>↵

[problem:1553C]↵

<spoiler summary="Solution">↵
[tutorial:1553C]↵
</spoiler>↵


<spoiler summary="Solution Code">↵
...↵
</spoiler>↵

[problem:1553D]↵

<spoiler summary="Solution">↵
[tutorial:1553D]↵
</spoiler>↵


<spoiler summary="Solution Code">↵
...↵
</spoiler>↵

[problem:1553E]↵

<spoiler summary="Solution">↵
[tutorial:1553E]↵
</spoiler>↵


<spoiler summary="Solution Code">↵
...↵
</spoiler>↵

[problem:1553F]↵

<spoiler summary="Solution">↵
[tutorial:1553F]↵
</spoiler>↵


<spoiler summary="Solution Code">↵
...↵
</spoiler>↵

[problem:1553G]↵

<spoiler summary="Solution">↵
[tutorial:1553G]↵
</spoiler>↵


<spoiler summary="Solution Code">↵
...↵
</spoiler>↵

[problem:1553H]↵

<spoiler summary="Solution">↵
[tutorial:1553H]↵
</spoiler>↵


<spoiler summary="Solution Code">↵
...↵
</spoiler>↵

[problem:1553I]↵

<spoiler summary="Solution">↵
[tutorial:1553I]↵
</spoiler>↵


<spoiler summary="Solution Code">↵
...
 We apologize for weak pretests and easy problems for top participants.↵

By the way, solution authors did not necessarily prepare the problems. The solutions were chosen at random. ↵

[problem:1553A]↵

Idea: [user:bthero,2021-07-22] Preparation: [user:kefaa2,2021-07-22]↵

<spoiler summary="Tutorial">↵
[tutorial:1553A]↵
</spoiler>↵


<spoiler summary="Solution (kefaa2)">↵
~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵
typedef long long ll;↵
int main() {↵
    //freopen("input.txt", "r", stdin);↵
    ios_base::sync_with_stdio(false);↵
    int tst;↵
    cin >> tst;↵
    while (tst--) {↵
        int n;↵
        cin >> n;↵
        cout << (n + 1) / 10 << '\n';↵
    }↵
}↵

~~~~~↵
</spoiler>↵

[problem:1553B] ↵

Idea: [user:Errichto,2021-07-22] Preparation: Will not be revealed for now because we care for his/their safety.↵

<spoiler summary="Tutorial">↵
[tutorial:1553B]↵
</spoiler>↵


<spoiler summary="Solution (BledDest)">↵
~~~~~↵
q = int(input())↵
for i in range(q):↵
s = input()↵
t = input()↵
n = len(s)↵
m = len(t)↵
ans = False↵
for i in range(n):↵
for j in range(0, n - i):↵
k = m - 1 - j↵
if i + j < k:↵
continue                                 ↵
l1 = i↵
r = i + j↵
l2 = r - k                                ↵
if s[l1:r+1] + s[l2:r][::-1] == t:↵
ans = True ↵
print('YES' if ans else 'NO')↵
~~~~~↵
</spoiler>↵

[problem:1553C]↵

Idea: [user:Errichto,2021-07-22] Preparation: [user:BledDest,2021-07-22]↵

<spoiler summary="Tutorial">↵
[tutorial:1553C]↵
</spoiler>↵


<spoiler summary="Solution (BledDest)">↵
~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

int main() {↵
int t;↵
cin >> t;↵
while (t--) {↵
string s;↵
cin >> s;↵
int ans = 9;↵

{↵
int cnt0 = 0, cnt1 = 0;↵
for (int i = 0; i < 10; ++i) {↵
if (i % 2 == 0) cnt0 += s[i] != '0';↵
else cnt1 += s[i] == '1'; ↵
if (cnt0 > cnt1 + (10 - i) / 2) ans = min(ans, i);↵
if (cnt1 > cnt0 + (9 - i) / 2) ans = min(ans, i);↵
}↵
}↵

{↵
int cnt0 = 0, cnt1 = 0;↵
for (int i = 0; i < 10; ++i) {↵
if (i % 2 == 0) cnt0 += s[i] == '1';↵
else cnt1 += s[i] != '0'; ↵
if (cnt0 > cnt1 + (10 - i) / 2) ans = min(ans, i);↵
if (cnt1 > cnt0 + (9 - i) / 2) ans = min(ans, i);↵
}↵
}↵

cout << ans + 1 << '\n';↵
}↵
}↵
~~~~~↵
</spoiler>↵

[problem:1553D]↵

Idea: [user:Adel_SaadEddin,2021-07-22], [user:Zaher,2021-07-22] Preparation: Will not be revealed for now because we care for his/their safety.↵

<spoiler summary="Tutorial">↵
[tutorial:1553D]↵
</spoiler>↵


<spoiler summary="Solution (BledDest)">↵
~~~~~↵
#include <iostream>↵
#include <cstdio>↵
#include <cstdlib>↵
#include <algorithm>↵
#include <cmath>↵
#include <vector>↵
#include <set>↵
#include <map>↵
#include <unordered_set>↵
#include <unordered_map>↵
#include <queue>↵
#include <ctime>↵
#include <cassert>↵
#include <complex>↵
#include <string>↵
#include <cstring>↵
#include <chrono>↵
#include <random>↵
#include <bitset>↵
using namespace std;↵

#ifdef LOCAL↵
#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);↵
#else↵
#define eprintf(...) 42↵
#endif↵

using ll = long long;↵
using ld = long double;↵
using uint = unsigned int;↵
using ull = unsigned long long;↵
template<typename T>↵
using pair2 = pair<T, T>;↵
using pii = pair<int, int>;↵
using pli = pair<ll, int>;↵
using pll = pair<ll, ll>;↵
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());↵
ll myRand(ll B) {↵
return (ull)rng() % B;↵
}↵

#define pb push_back↵
#define mp make_pair↵
#define all(x) (x).begin(),(x).end()↵
#define fi first↵
#define se second↵

clock_t startTime;↵
double getCurrentTime() {↵
return (double)(clock() - startTime) / CLOCKS_PER_SEC;↵
}↵

const int N = 200200;↵
int n, m;↵
char s[N], t[N];↵

bool solve() {↵
scanf("%s %s", s, t);↵
n = strlen(s);↵
m = strlen(t);↵
if (n < m) return false;↵
int p = (n - m) & 1;↵
int q = 0;↵
int k = 0;↵
for (int i = p; i < n; i++) {↵
if (k == 1) {↵
k = 0;↵
continue;↵
}↵
if (q < m && s[i] == t[q]) {↵
q++;↵
} else {↵
k++;↵
}↵
}↵
return q == m;↵
}↵

int main()↵
{↵
startTime = clock();↵
// freopen("input.txt", "r", stdin);↵
// freopen("output.txt", "w", stdout);↵

int T;↵
scanf("%d", &T);↵
while(T--) {↵
if (solve())↵
printf("YES\n");↵
else↵
printf("NO\n");↵
}↵

return 0;↵
}↵

~~~~~↵
</spoiler>↵

[problem:1553E]↵

Idea: [user:bthero,2021-07-22], [user:kefaa2,2021-07-22] Preparation: [user:BledDest,2021-07-22]↵

<spoiler summary="Tutorial">↵
[tutorial:1553E]↵
</spoiler>↵


<spoiler summary="Solution (BledDest)">↵
~~~~~↵
#include <bits/stdc++.h>     ↵

using namespace std; ↵

int cycle_count(vector<int> q, int n)↵
{↵
  for(int i = 0; i < n; i++)↵
  q[i]--;↵
  vector<int> used(n);↵
  int ans = 0;↵
  for(int i = 0; i < n; i++)↵
  {↵
  if(used[i] == 1) continue;↵
  int j = i;↵
  while(used[j] == 0)↵
  {↵
    used[j] = 1;↵
    j = q[j];↵
  }↵
  ans++;↵
  }↵
  return ans;↵
}↵

bool check(int n, int m, int k, vector<int> p)↵
{↵
  vector<int> q;↵
  for(int i = k; i < n; i++)↵
  q.push_back(p[i]);↵
  for(int i = 0; i < k; i++)↵
  q.push_back(p[i]);↵
  return n - cycle_count(q, n) <= m;↵
}↵

void solve()↵
{↵
  int n, m;↵
  scanf("%d %d", &n, &m);↵
  vector<int> p(n);↵
  for(int i = 0; i < n; i++)↵
  scanf("%d", &p[i]);↵
  vector<int> cnt(n);↵
  for(int i = 0; i < n; i++)↵
  {↵
    int offset = i + 1 - p[i];↵
    if(offset < 0)↵
    offset += n;↵
    cnt[offset]++;↵
  }↵
  vector<int> ans;↵
  for(int i = 0; i < n; i++)↵
  if(cnt[i] + 2 * m >= n && check(n, m, i, p))↵
  ans.push_back(i);↵
  printf("%d", ans.size());↵
  for(auto x : ans) printf(" %d", x);↵
  puts("");↵
  ↵
}↵

int main()↵
{↵
int t;↵
scanf("%d", &t);↵
for(int i = 0; i < t; i++)↵
{↵
solve();  ↵
}↵
}↵
~~~~~↵
</spoiler>↵

[problem:1553F]↵

Idea: [user:kefaa2,2021-07-22], [user:Errichto,2021-07-22] Preparation: [user:bthero,2021-07-22]↵

<spoiler summary="Tutorial"> ↵
[tutorial:1553F]↵
</spoiler>↵


<spoiler summary="Solution (bthero)">↵
~~~~~↵
// chrono::system_clock::now().time_since_epoch().count()↵
#include <bits/stdc++.h>↵

using namespace std;↵

typedef long long ll;↵

template<int N> struct Fenw {↵
    ll t[N + 1];↵

    Fenw() {↵
        fill(t + 1, t + N + 1, 0ll);↵
    }↵

    void update(int p, ll x) {↵
        for (; p <= N; p |= (p + 1)) {↵
            t[p] += x;↵
        }↵
    }↵

    ll get(int p) {↵
        ll ret = 0;↵

        for (; p > 0; --p) {↵
            ret += t[p];↵
            p &= (p + 1);↵
        }↵

        return ret;↵
    }↵

    ll get(int l, int r) {↵
        return get(r) - get(l - 1);↵
    }↵
};↵

const int M = (int)3e5;↵

void solve() {↵
    int n;↵
    cin >> n;↵
    Fenw<M> A, B;↵
    ll pref = 0, ans = 0;↵

    for (int i = 1; i <= n; ++i) {↵
        int x;↵
        cin >> x;↵
        ans += x * (i - 1ll);↵
        ans += A.get(x);↵
        ans += pref;↵
        pref += x;↵
        ↵
        for (int j = x; j <= M; j += x) {↵
            int l = j, r = min(M, j + x - 1);↵
            ans -= B.get(l, r) * j;↵
            A.update(l, -x);↵
        }↵

        B.update(x, 1);↵
        cout << ans << " \n"[i == n];↵
    }↵
}↵

int main() {↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(0);↵
    cout.tie(0);↵

    int tt = 1;↵

    for (int i = 1; i <= tt; ++i) {↵
        solve();↵
    }↵

    return 0;↵
}↵
~~~~~↵
</spoiler>↵

[problem:1553G]↵

Idea: [user:Adel_SaadEddin,2021-07-22], [user:Zaher,2021-07-22], [user:Errichto,2021-07-22] Preparation: [user:Errichto,2021-07-22]↵

<spoiler summary="Tutorial">↵
[tutorial:1553G]↵
</spoiler>↵


<spoiler summary="Solution (Errichto)">↵
~~~~~↵
// gcd, AC, O((N+Q) * log^2), by Errichto↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define sim template < class c↵
#define ris return * this↵
#define dor > debug & operator <<↵
#define eni(x) sim > typename \↵
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {↵
sim > struct rge { c b, e; };↵
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }↵
sim > auto dud(c* x) -> decltype(cerr << *x, 0);↵
sim > char dud(...);↵
struct debug {↵
#ifdef LOCAL↵
~debug() { cerr << endl; }↵
eni(!=) cerr << boolalpha << i; ris; }↵
eni(==) ris << range(begin(i), end(i)); }↵
sim, class b dor(pair < b, c > d) {↵
  ris << "(" << d.first << ", " << d.second << ")";↵
}↵
sim dor(rge<c> d) {↵
  *this << "[";↵
  for (auto it = d.b; it != d.e; ++it)↵
*this << ", " + 2 * (it == d.b) << *it;↵
  ris << "]";↵
}↵
#else↵
sim dor(const c&) { ris; }↵
#endif↵
};↵
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "↵
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }↵

struct DSU {↵
vector<int> parent;↵
DSU(int m) {↵
parent.resize(m + 1);↵
for(int i = 0; i <= m; ++i) {↵
parent[i] = i;↵
}↵
}↵
int find(int a) {↵
if(a == parent[a]) {↵
return a;↵
}↵
return parent[a] = find(parent[a]);↵
}↵
void uni(int a, int b) {↵
parent[find(a)] = find(b);↵
}↵
};↵

int main() {↵
// 1) read input↵
int n, q;↵
scanf("%d%d", &n, &q);↵
vector<int> a(n);↵
for(int i = 0; i < n; ++i) {↵
scanf("%d", &a[i]);↵
}↵
int m = *max_element(a.begin(), a.end());↵
// 2) prime sieve↵
vector<vector<int>> prime_divisors(m + 2);↵
for(int p = 2; p <= m + 1; ++p) {↵
if(prime_divisors[p].empty()) {↵
for(int j = p; j <= m + 1; j += p) {↵
prime_divisors[j].push_back(p);↵
}↵
}↵
}↵
// 3) DSU, find initial connected components↵
DSU dsu(m + 2);↵
for(int x : a) {↵
for(int p : prime_divisors[x]) {↵
dsu.uni(x, p);↵
}↵
}↵
// 4) DSU, find edges of cost 1↵
set<pair<int,int>> edges;↵
for(int x : a) {↵
vector<int> nodes = prime_divisors[x+1];↵
nodes.push_back(x);↵
for(int& node : nodes) {↵
node = dsu.find(node);↵
}↵
for(int i = 0; i < (int) nodes.size(); ++i) {↵
for(int j = i + 1; j < (int) nodes.size(); ++j) {↵
int one = nodes[i];↵
int two = nodes[j];↵
if(one != two) {↵
if(one > two) {↵
swap(one, two);↵
}↵
edges.insert({one, two});↵
}↵
}↵
}↵
}↵
debug() << imie(edges);↵
cerr << imie(edges.size()) << endl;↵
// 5) answer queries↵
while(q--) {↵
int s, t;↵
scanf("%d%d", &s, &t);↵
--s;↵
--t;↵
s = dsu.find(a[s]);↵
t = dsu.find(a[t]);↵
if(s == t) {↵
puts("0");↵
}↵
else if(edges.count({min(s, t), max(s, t)})) {↵
puts("1");↵
}↵
else {↵
puts("2");↵
}↵
}↵
}↵
~~~~~↵
</spoiler>↵

[problem:1553H]↵

Idea: [user:kefaa2,2021-07-22] Preparation: [user:BledDest,2021-07-22], [user:MarX,2021-07-22], [user:kefaa2,2021-07-22]↵

<spoiler summary="Tutorial">↵
[tutorial:1553H]↵
</spoiler>↵


<spoiler summary="Solution (BledDest)">↵
~~~~~↵
#include<bits/stdc++.h>↵

using namespace std;↵

const int INF = int(1e9);↵
const int K = 20;↵

struct node↵
{↵
  int max_val, min_val, ans, len;↵
  ↵
  node(const node& left, const node& right)↵
  {↵
  len = left.len + right.len;↵
  max_val = max(left.max_val, right.max_val + left.len);↵
  min_val = min(left.min_val, right.min_val + left.len);↵
    ans = min(min(left.ans, right.ans), min(INF, right.min_val - left.max_val + left.len));↵
  }↵

  node(int x)↵
  {↵
    ans = INF;↵
    len = 1;↵
    if(x == 1)↵
      max_val = min_val = 0;↵
    else↵
    {↵
      max_val = -INF;↵
      min_val = INF;↵
    }↵
  }↵

  node() {};↵
};↵

int cnt[1 << K];↵
vector<node> tree[2 << K]; ↵

void build(int v, int l, int r)↵
{↵
tree[v].resize(r - l);↵
  if(l == r - 1)↵
  {↵
  tree[v][0] = node(cnt[l]); ↵
  }↵
  else↵
  {↵
    int m = (l + r) / 2;↵
    build(v * 2 + 1, l, m);↵
    build(v * 2 + 2, m, r);↵
    for(int i = 0; i < m - l; i++)↵
    {↵
    tree[v][i] = node(tree[v * 2 + 1][i], tree[v * 2 + 2][i]);↵
    tree[v][i + (m - l)] = node(tree[v * 2 + 2][i], tree[v * 2 + 1][i]);  ↵
    }↵
  }↵
}↵

int main()↵
{            ↵
int n, k;↵
scanf("%d %d", &n, &k);↵
for(int i = 0; i < n; i++)↵
{↵
int x;↵
  scanf("%d", &x);↵
  cnt[x]++;↵
}↵
int m = 1 << k;↵
build(0, 0, m);↵
for(int i = 0; i < m; i++)↵
printf("%d ", tree[0][i].ans);↵
puts("");↵
}↵
~~~~~↵
</spoiler>↵

[problem:1553I]↵

Idea: [user:bthero,2021-07-22], [user:kefaa2,2021-07-22], [user:BledDest,2021-07-22] Preparation: [user:BledDest,2021-07-22], [user:kefaa2,2021-07-22]↵

<spoiler summary="Tutorial">↵
[tutorial:1553I]↵
</spoiler>↵


<spoiler summary="Solution (BledDest)">↵
~~~~~↵
#include<bits/stdc++.h>↵

using namespace std;↵

#define forn(i, n) for(int i = 0; i < int(n); i++)↵
#define sz(a) ((int)((a).size()))↵
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)↵

template<const int &MOD>↵
struct _m_int {↵
int val;↵
 ↵
_m_int(int64_t v = 0) {↵
if (v < 0) v = v % MOD + MOD;↵
if (v >= MOD) v %= MOD;↵
val = int(v);↵
}↵
 ↵
_m_int(uint64_t v) {↵
if (v >= MOD) v %= MOD;↵
val = int(v);↵
}↵
 ↵
_m_int(int v) : _m_int(int64_t(v)) {}↵
_m_int(unsigned v) : _m_int(uint64_t(v)) {}↵
 ↵
static int inv_mod(int a, int m = MOD) {↵
int g = m, r = a, x = 0, y = 1;↵
 ↵
while (r != 0) {↵
int q = g / r;↵
g %= r; swap(g, r);↵
x -= q * y; swap(x, y);↵
}↵
 ↵
return x < 0 ? x + m : x;↵
}↵
 ↵
explicit operator int() const { return val; }↵
explicit operator unsigned() const { return val; }↵
explicit operator int64_t() const { return val; }↵
explicit operator uint64_t() const { return val; }↵
explicit operator double() const { return val; }↵
explicit operator long double() const { return val; }↵
 ↵
_m_int& operator+=(const _m_int &other) {↵
val -= MOD - other.val;↵
if (val < 0) val += MOD;↵
return *this;↵
}↵
 ↵
_m_int& operator-=(const _m_int &other) {↵
val -= other.val;↵
if (val < 0) val += MOD;↵
return *this;↵
}↵
 ↵
static unsigned fast_mod(uint64_t x, unsigned m = MOD) {↵
#if !defined(_WIN32) || defined(_WIN64)↵
return unsigned(x % m);↵
#endif↵
// Optimized mod for Codeforces 32-bit machines.↵
// x must be less than 2^32 * m for this to work, so that x / m fits in an unsigned 32-bit int.↵
unsigned x_high = unsigned(x >> 32), x_low = unsigned(x);↵
unsigned quot, rem;↵
asm("divl %4\n"↵
: "=a" (quot), "=d" (rem)↵
: "d" (x_high), "a" (x_low), "r" (m));↵
return rem;↵
}↵
 ↵
_m_int& operator*=(const _m_int &other) {↵
val = fast_mod(uint64_t(val) * other.val);↵
return *this;↵
}↵
 ↵
_m_int& operator/=(const _m_int &other) {↵
return *this *= other.inv();↵
}↵
 ↵
friend _m_int operator+(const _m_int &a, const _m_int &b) { return _m_int(a) += b; }↵
friend _m_int operator-(const _m_int &a, const _m_int &b) { return _m_int(a) -= b; }↵
friend _m_int operator*(const _m_int &a, const _m_int &b) { return _m_int(a) *= b; }↵
friend _m_int operator/(const _m_int &a, const _m_int &b) { return _m_int(a) /= b; }↵
 ↵
_m_int& operator++() {↵
val = val == MOD - 1 ? 0 : val + 1;↵
return *this;↵
}↵
 ↵
_m_int& operator--() {↵
val = val == 0 ? MOD - 1 : val - 1;↵
return *this;↵
}↵
 ↵
_m_int operator++(int) { _m_int before = *this; ++*this; return before; }↵
_m_int operator--(int) { _m_int before = *this; --*this; return before; }↵
 ↵
_m_int operator-() const {↵
return val == 0 ? 0 : MOD - val;↵
}↵
 ↵
friend bool operator==(const _m_int &a, const _m_int &b) { return a.val == b.val; }↵
friend bool operator!=(const _m_int &a, const _m_int &b) { return a.val != b.val; }↵
friend bool operator<(const _m_int &a, const _m_int &b) { return a.val < b.val; }↵
friend bool operator>(const _m_int &a, const _m_int &b) { return a.val > b.val; }↵
friend bool operator<=(const _m_int &a, const _m_int &b) { return a.val <= b.val; }↵
friend bool operator>=(const _m_int &a, const _m_int &b) { return a.val >= b.val; }↵
 ↵
_m_int inv() const {↵
return inv_mod(val);↵
}↵
 ↵
_m_int pow(int64_t p) const {↵
if (p < 0)↵
return inv().pow(-p);↵
 ↵
_m_int a = *this, result = 1;↵
 ↵
while (p > 0) {↵
if (p & 1)↵
result *= a;↵
a *= a;↵
p >>= 1;↵
}↵
 ↵
return result;↵
}↵
 ↵
friend ostream& operator<<(ostream &os, const _m_int &m) {↵
return os << m.val;↵
}↵
};↵
 ↵
extern const int MOD = 998244353;↵
using Mint = _m_int<MOD>;↵

const int LOGN = 19;↵
const int N = (1 << LOGN);↵
const int T = 2;          ↵
Mint g = 3;↵

vector<Mint> w[LOGN];↵
vector<int> rv[LOGN];↵

void precalc() {↵
Mint wb = Mint(g).pow((MOD - 1) / (1 << LOGN));↵
forn(st, LOGN - 1) {↵
w[st].assign(1 << st, 1);↵
Mint bw = wb.pow(1 << (LOGN - st - 1));↵
Mint cw = 1;↵
forn(k, 1 << st) {↵
w[st][k] = cw;↵
cw *= bw;↵
}↵
}↵
forn(st, LOGN) {↵
rv[st].assign(1 << st, 0);↵
if (st == 0) {↵
rv[st][0] = 0;↵
continue;↵
}↵
int h = (1 << (st - 1));↵
forn(k, 1 << st)↵
rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);↵
}↵
}↵

void ntt(vector<Mint> &a, bool inv) {↵
int n = sz(a);↵
int ln = __builtin_ctz(n);↵
forn(i, n) {↵
int ni = rv[ln][i];↵
if (i < ni) swap(a[i], a[ni]);↵
}↵
forn(st, ln) {↵
int len = 1 << st;↵
for (int k = 0; k < n; k += (len << 1)) {↵
fore(pos, k, k + len){↵
Mint l = a[pos];↵
Mint r = a[pos + len] * w[st][pos - k];↵
a[pos] = l + r;↵
a[pos + len] = l - r;↵
}↵
}↵
}↵
if (inv) {↵
Mint rn = Mint(n).inv();↵
forn(i, n) a[i] *= rn;↵
reverse(a.begin() + 1, a.end());↵
}↵
}↵

vector<Mint> mul(vector<Mint> a, vector<Mint> b) {↵
int cnt = 1 << (32 - __builtin_clz(sz(a) + sz(b) - 1));↵
a.resize(cnt);↵
b.resize(cnt);↵
ntt(a, false);↵
ntt(b, false);↵
vector<Mint> c(cnt);↵
forn(i, cnt) c[i] = a[i] * b[i];↵
ntt(c, true);↵
while(c.size() > 1 && c.back() == 0)↵
c.pop_back();↵
return c;↵
}↵

struct dp↵
{↵
  vector<Mint> val[T][T];↵
  bool is_unit;↵

  dp() {};↵
  dp(int len)↵
  {↵
  is_unit = len == 1;↵
  for(int j = 0; j < T; j++)↵
  for(int k = 0; k < T; k++)↵
  val[j][k] = {0};↵
  if(len == 1)↵
  val[0][0][0] = 1;↵
  else↵
  val[1][1][0] = 2;↵
  }↵

  dp(const dp& a, const dp& b)↵
  {↵
  is_unit = false;↵
  for(int l1 = 0; l1 < T; l1++)↵
  for(int r1 = 0; r1 < T; r1++)↵
  for(int l2 = 0; l2 < T; l2++)↵
  for(int r2 = 0; r2 < T; r2++)↵
  {↵
    vector<Mint> cur = mul(a.val[l1][r1], b.val[l2][r2]);↵
    if(val[l1][r2].size() < cur.size())↵
    val[l1][r2].resize(cur.size());↵
    for(int i = 0; i < cur.size(); i++)↵
  val[l1][r2][i] += cur[i];↵
    Mint merge_coeff = 2;↵
    if(r1 == 1)↵
    merge_coeff /= 2;↵
    if(l2 == 1)↵
    merge_coeff /= 2;↵
    cur.insert(cur.begin(), 0);↵
    for(int i = 0; i < cur.size(); i++)↵
    cur[i] *= merge_coeff;↵
    int L1 = l1;↵
    int R2 = r2;↵
    if(a.is_unit)↵
    L1 = 1;↵
    if(b.is_unit)↵
    R2 = 1;↵
    if(val[L1][R2].size() < cur.size())↵
    val[L1][R2].resize(cur.size());↵
    for(int i = 0; i < cur.size(); i++)↵
    {↵
    val[L1][R2][i] += cur[i];↵
  }↵
    }↵
  }↵
};↵

ostream& operator<<(ostream& out, const dp& a)↵
{↵
  for(int i = 0; i < T; i++)↵
  for(int j = 0; j < T; j++)↵
  {↵
    out << "[" << i << "][" << j << "]";↵
    for(auto x : a.val[i][j])↵
    out << " " << x;↵
    out << endl;↵
  }↵
  return out;↵
}↵

int a[N];↵
int len[N];↵
Mint fact[N];↵
int n;↵
int s;↵

dp build(int l, int r)↵
{↵
  if(l == r - 1)↵
  {↵
  dp res(len[l]);   ↵
  //cerr << l << " " << r << endl;↵
    //cerr << res;↵
    return res;↵
  }                     ↵
  else↵
  {↵
  int m = (l + r) / 2;↵
  dp res(build(l, m), build(m, r));↵
  //cerr << l << " " << r << endl;↵
  //cerr << res;↵
  return res;                         ↵
  }↵
}↵

int main()↵
{↵
precalc();↵
scanf("%d", &n);↵
for(int i = 0; i < n; i++)↵
  scanf("%d", &a[i]);↵
int cur = 0;↵
while(cur != n)↵
{↵
  if(cur + a[cur] > n)↵
  {↵
          cout << 0 << endl;↵
          return 0;↵
        }↵
        for(int l = cur; l < cur + a[cur]; l++)↵
         if(a[l] != a[cur])↵
         {↵
           cout << 0 << endl;↵
           return 0;↵
         }↵
        len[s++] = a[cur];↵
        cur += a[cur];↵
}↵

fact[0] = 1;↵
for(int i = 1; i <= s; i++)↵
fact[i] = i * fact[i - 1];↵

dp res = build(0, s);↵

Mint ans = 0;↵
for(int i = 0; i < s; i++)            ↵
for(int j = 0; j < T; j++)↵
for(int k = 0; k < T; k++)↵
if(res.val[j][k].size() > i)↵
ans += fact[s - i] * res.val[j][k][i] * (i % 2 == 0 ? 1 : MOD - 1);↵
cout << ans << endl;↵
}↵
~~~~~

</spoiler>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English Harbour.Space 2021-07-23 11:29:22 3035 Tiny change: 'h you all happy upsolving' -> 'h you all productive upsolving'
en3 English Harbour.Space 2021-07-22 22:56:50 2122 Tiny change: ' summary="Solution (B' -> ' summary="Alternative solution (B'
en2 English Harbour.Space 2021-07-22 22:35:06 21493 Tiny change: ':bthero]\nPreparat' -> ':bthero]\n\nPreparat' (published)
en1 English Harbour.Space 2021-07-22 21:58:50 1396 Initial revision (saved to drafts)