If there is a subarray containing $$$k - 1$$$ zeros, then the next element cannot be prevented from being hit. So any time we see $$$k - 1$$$ zeros follwed by a one then the one must be protected.

From Hint 1, lets protect every $$$\mathtt{1}$$$ that fits the pattern. Furthermore we should always protect the first $$$1$$$ in the string so lets do that. It turns out that this is all that we need to do, to prove this think inductively: every element that is not protected will always have a $$$\mathtt{1}$$$ in the last $$$k - 1$$$ elements and so it will be unchanged. So to solve the problem we can check the distance between each consecutive $$$\mathtt{1}$$$, if the gap is at least $$$k$$$ then add $$$1$$$ to the answer. Final time complexity $$$O(n)$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void solve(){
    int n, k;
    cin >> n >> k;

    string s;
    cin >> s;

    int ans = 0;
    int last = -1e9;
    for (int i = 0; i < n; i++){
        if (s[i] == '1' && i - last >= k)
            ans++;
        if (s[i] == '1')
            last = i;
    }

    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

https://youtu.be/5Xku9F6Rbqo

You want odd-indexed values to be small, and even-indexed values to be large. In other words, it is beneficial to apply operation 1 on even indices, and operation 2 on odd indices.

Since operation 1 is free, you may as well apply it to every even index. None of the operations can increase a prefix max, so you can't possibly do any better than just applying operation 1 immediately to every even index.

Let's first apply operation 1 to every even index. Now, we can't further increase any even-indexed values, so we just need to decrease odd-indexed values by using operation 2. All of the odd indices are independent from one another, so let's just consider each one separately. For a fixed odd index $$$i$$$, the number of instances of operation 2 needed to make it smaller than $$$a_{i-1}$$$ and $$$a_{i+1}$$$ is given by $$$\max(0, a_i - \min(a_{i-1}, a_{i+1}) + 1)$$$. (Be careful with indices $$$1$$$ and $$$n$$$ as well; you can treat the out of bounds values as being arbitrarily large, or just take care of them separately.) Now, we sum this value, across all odd indices $$$i$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void solve(){
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    vector<int> pre(n);
    pre[0] = a[0];
    for (int i = 1; i < n; i++)
        pre[i] = max(pre[i - 1], a[i]);

    ll ans = 0;
    for (int i = 0; i < n; i += 2){
        int dif = -1;
        if (i > 0)
            dif = max(dif, a[i] - pre[i - 1]);

        if (i < n - 1)
            dif = max(dif, a[i] - pre[i + 1]);

        ans += dif + 1;
    }

    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

You can make an element divisible by $$$2$$$ in $$$1$$$ move.

Can you check if the answer is $$$0$$$ or if the answer is $$$1$$$?

By result of Hint 1, the answer cannot be more than $$$2$$$, as we can always pick two elements and make them both divisible by $$$2$$$ using at most $$$1$$$ move on each. So now we just need to check if the answer is $$$0$$$ or $$$1$$$.

To check if the answer is $$$0$$$, we need to determine if there is a common divisor between two elements. Note that it is sufficient to only check if there is a common prime divisor. So, for each element, iterate through all its prime divisors and check if there is another element with the same prime divisor.

To check if the answer is $$$1$$$, we can do the same as $$$0$$$. This time, for each $$$i$$$ we check if $$$a_i + 1$$$ shares a common prime divisor with another element.

Prime divisors can be pre-calculated with the Sieve of Eratosthenes in $$$O(N\log\log N)$$$ where $$$N$$$ is the maximum possible element (so $$$2 \cdot 10^5$$$ for this problem). However, the constraints are lenient enough to allow $$$O(n\sqrt{N})$$$ as well.

The final complexity comes out to $$$O(n\omega(N) + N\log\log N)$$$, where $$$\omega(x)$$$ is used to denote the number of distinct prime divisors of $$$x$$$. Note that the editorial implementation is $$$O(n\omega(N)\log(n\omega(N)) + N\log\log N)$$$ due to use of c++ std::map for the sake of readability.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

const int N = 2e5 + 10;
vector<vector<int>> pfac(N + 1);

void solve(){
    int n;
    cin >> n;

    vector<int> a(n), b(n);
    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;

    int ans = 2;
    map<int, int> cnt;
    for (int i = 0; i < n; i++){
        for (int x : pfac[a[i]]){
            if (cnt[x] > 0)
                ans = 0;
            cnt[x]++;
        }
    }

    for (int i = 0; i < n; i++){
        for (int x : pfac[a[i]])
            cnt[x]--;

        for (int x : pfac[a[i] + 1]){
            if (cnt[x] > 0)
                ans= min(ans, 1);
        }

        for (int x : pfac[a[i]])
            cnt[x]++;
    }

    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    for (int i = 2; i <= N; i++){
        if (!pfac[i].empty())
            continue;

        for (int j = i; j <= N; j += i)
            pfac[j].push_back(i);
    }
    
    int t;
    cin >> t;
    while (t--) solve();
}

Solve the easy version.

We can always make two elements $$$i, j$$$ divisible by $$$2$$$ with no more than $$$b_i + b_j$$$ cost.

By hint 2, we should never perform more than one operation on more than one element.

Lets say we are trying to make the elements at index $$$i, j$$$ have a common divisor. From hint 2 and 3 there are only two cases to consider here. The first case where we make $$$0$$$ or $$$1$$$ operation on both $$$i$$$ and $$$j$$$. Or the second case where we make more than $$$1$$$ operation on a single element. We should never do more than $$$1$$$ operation on both elements because we can always do better by making both elements divisible by $$$2$$$.

So now to solve the problem on the entire array, we should try to solve both of the cases. For convenience lets reorder the elements so that $$$b$$$ is in sorted order.

The first case can be solve almost identically to the easy version of the problem. We can always do at least as good as $$$b_1 + b_2$$$, the only other possibility is only making one operation. To do this we just check if $$$a_i + 1$$$ has a common prime divisor with another element.

The second case is the more tricky case, we need to check the optimal way to make more than one operations for each element, and it is probably the crux of the problem. The key thing to notice is that we actually do not need to check every element, in fact we can only check the element with the smallest value of $$$b_i$$$ ($$$b_1$$$ because $$$b$$$ is sorted). To prove this lets argue by contradiction, supposed we made $$$k$$$ ($$$k \ge 2$$$) operations on element $$$x$$$ ($$$x \ge 2$$$). The total cost of this is $$$k \cdot b_x$$$, we know from hint 2 that we can do $$$b_1 + b_x$$$ or better, since $$$b_1$$$ is the smallest element we know that $$$b_1 + b_x \le k \cdot b_x$$$ and thus we do not need to consider this case!

So now we need to quickly check what is the optimal way to use multiple operations on the first element. To do this we can iterate through all the prime divisors of the other elements and determine the minimum number of operations to make $$$a_1$$$ divisible by it.

The final time complexity comes out to $$$O(n\omega(N) + N\log\log N)$$$, where $$$\omega(x)$$$ is used to denote the number of distinct prime divisors of $$$x$$$. Note that the editorial implementation is $$$O(n\omega(N)\log(n\omega(N)) + N\log\log N)$$$ due to use of c++ std::map for the sake of readability.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

const int N = 2e5 + 10;
vector<vector<int>> pfac(N + 1);

void solve(){
    int n;
    cin >> n;

    vector<int> a(n), b(n);
    for (int &x : a) cin >> x;
    for (int &x : b) cin >> x;

    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int x, int y) -> bool{
        return b[x] < b[y];
    });

    int ans = b[ord[0]] + b[ord[1]];
    map<int, int> cnt;
    for (int i = 0; i < n; i++){
        for (int x : pfac[a[i]]){
            if (cnt[x] > 0)
                ans = 0;
            cnt[x]++;
        }
    }

    for (int i = 0; i < n; i++){
        for (int x : pfac[a[i]])
            cnt[x]--;

        for (int x : pfac[a[i] + 1]){
            if (cnt[x] > 0)
                ans= min(ans, b[i]);
        }

        for (int x : pfac[a[i]])
            cnt[x]++;
    }

    int idx = ord[0];
    vector<int> check;
    for (int i = 0; i < n; i++){
        if (i == idx)
            continue;

        for (int x : pfac[a[i]])
            check.push_back(x);
    }

    for (int x : check){
        int times = x - (a[idx] % x);
        if (times == x)
            times = 0;

        ans = min(1LL * ans, 1LL * times * b[idx]);
    }

    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    for (int i = 2; i <= N; i++){
        if (!pfac[i].empty())
            continue;

        for (int j = i; j <= N; j += i)
            pfac[j].push_back(i);
    }
    
    int t;
    cin >> t;
    while (t--) solve();
}

Destroying a leaf will never split the tree.

Trees are bipartite. In particular, you can root the tree arbitrarily, then partition vertices into those with even depth and those with odd depth. All edges connect an even depth vertex to an odd depth vertex.

We would like to decrease the size of the tree by one vertex using no more than three moves. To do so, we will pick an arbitrary leaf $$$v$$$ and destroy it. However, we must make sure that we do not destroy the vertex we are standing on, and that we do not have two consecutive instances of the second instruction. To do so, let's root the tree arbitrarily, and color vertices with even depth red and vertices with odd depth blue. We maintain the color of the vertex we are standing on, noting that every instance of instruction 1 flips the color. Now, if we are standing on the same color as $$$v$$$, we apply operation 1 once. Otherwise, we apply operation 1 twice. Thus, we are not currently standing on leaf $$$v$$$, so now we can destroy $$$v$$$. Since we applied at least one instance of instruction 1, we do not have two consecutive instances of instruction 2. By iterating this process until the only remaining vertex is vertex $$$n$$$, we guarantee that we have reached vertex $$$n$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void solve(){
    int n;
    cin >> n;

    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        u--;
        v--;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> dep(n), par(n), ch(n);
    auto dfs = [&](auto self, int c, int p) -> void{
        if (p != -1)
            dep[c] = dep[p] + 1;
        par[c] = p;
        
        for (int x : g[c]){
            if (x == p) continue;
            
            self(self, x, c);
            ch[c]++;
        }
    };
    dfs(dfs, n - 1, -1);

    array<vector<int>, 2> leaves;
    leaves[0];

    for (int i = 0; i < n; i++){
        if (ch[i] == 0)
            leaves[dep[i] & 1].push_back(i);
    }

    vector<array<int, 2>> ans;
    int col = dep[0] & 1;
    for (int i = 0; i < n - 1; i++){
        if (leaves[col ^ 1].empty()){
            ans.push_back({1, -1});
            col ^= 1;
        }

        int nxt = leaves[col ^ 1].back();
        leaves[col ^ 1].pop_back();
        ans.push_back({2, nxt});

        int p = par[nxt];
        ch[p]--;
        if (ch[p] == 0)
            leaves[dep[p] & 1].push_back(p);

        ans.push_back({1, -1});
        col ^= 1;
    }

    cout << ans.size() << "\n";
    for (auto [x, y] : ans){
        if (x == 1)
            cout << "1\n";
        else
            cout << "2 " << y + 1 << "\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

Can you implement the checker?

Without loss of generality, assume the array is sorted. Let's fix $$$x = 2y+1$$$, and let's also fix the median of a given operation $$$a_i$$$, for some $$$y+1 \leq i\leq n-y$$$. Now, we see that the best subsequence to choose is $$$a_1, a_2, \dots, a_y, a_i, a_{i+1}, \dots, a_{i+y}$$$, because we must choose $$$y$$$ values to the left of $$$a_i$$$ and $$$y$$$ values to the right of $$$a_i$$$, and we would like to change the smallest values possible.

Suppose you have applied one operation with median $$$a_i$$$ and another operation with median $$$a_j$$$, for $$$y+1 \leq i \lt j \leq n-y$$$. Now, you have increased up to $$$\min(2y, j-1)$$$ of the smallest values to either $$$a_i$$$ or $$$a_j$$$, since you can increase up to $$$y$$$ values smaller than the median each operation. However, you have also decreased $$$y$$$ values after $$$a_i$$$, and $$$y$$$ values after $$$a_j$$$. Instead, you might as well have just applied two operations with median $$$a_j$$$, which allows you to increase $$$\min(2y, j-1)$$$ of the smallest values to $$$a_j$$$, and decrease only the $$$y$$$ values after $$$a_j$$$. Therefore, there exists some optimal sequence of operations where we use the same median across all operations.

By the result of Hint 2, there exists some optimal sequence of operations where we use the same median across all operations. Let's fix the median at $$$a_i$$$. Now, if we choose $$$x = 2y+1$$$ for some $$$0\leq y \leq \min(i-1, n-i)$$$, we are able to increase the values of $$$a_1, a_2, \dots, a_{\min(ky, i-1)}$$$ to $$$a_i$$$, but we must also decrease the values of $$$a_{i+1}, a_{i+2}, \dots, a_{i+y}$$$ to $$$a_i$$$.

The benefits of increasing $$$y$$$ are that we can increase more values, but notice that these benefits are getting less and less, because we are increasing values that are already larger. For example, the benefit of increasing $$$y$$$ from $$$0$$$ to $$$1$$$ is that now we can increase the values $$$a_1, a_2, \dots, a_k$$$, but the benefit from increasing $$$y$$$ from $$$1$$$ to $$$2$$$ is that now we can increase the values $$$a_{k+1}, a_{k+2}, \dots, a_{2k}$$$; increasing $$$y$$$ from $$$1$$$ to $$$2$$$ is not as beneficial as increasing $$$y$$$ from $$$0$$$ to $$$1$$$, because the values we are increasing are already relatively big. (There's a small case to think about, when $$$ky$$$ first exceeds $$$i-1$$$, but note that the number of values you can increase is also monotonically decreasing, so this doesn't cause any issues.) The same reasoning goes for the losses. The losses of increasing $$$y$$$ are that we are forced to decrease more values, and these losses are getting greater and greater. If we increase $$$y$$$ from $$$0$$$ to $$$1$$$, we are only forced to decrease $$$a_{i+1}$$$, but if we increase $$$y$$$ from $$$1$$$ to $$$2$$$, we now have to decrease $$$a_{i+2}$$$, which is worse because $$$a_{i+2}$$$ is relatively big. In other words, our net gains (that is, the benefits minus the losses) are monotonically decreasing.

We want to keep incrementing $$$y$$$ as long as our net gains are positive, then stop incrementing $$$y$$$ once our net gains become negative. Since our net gains are monotonically decreasing, we can binary search for this point. (Alternative solutions might use ternary search instead.) So we iterate over all choices of $$$i$$$, then binary search for the optimal choice of $$$y$$$, which in total takes $$$O(n\log{n})$$$ time. Note that all computations can be done quickly with prefix sums.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

void solve(){
    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (int &x : a) cin >> x;

    sort(a.begin(), a.end());

    vector<ll> pre(n);
    pre[0] = a[0];
    for (int i = 1; i < n; i++)
        pre[i] = pre[i - 1] + a[i];

    ll ans = pre[n - 1];

    auto query = [&](int l, int r) -> ll{
        ll res = pre[r];
        if (l > 0)
            res -= pre[l - 1];
        return res;
    };

    for (int i = 0; i < n; i++){
        int l = 1, r = min(i, n - i - 1) + 1;
        while (l < r){
            int mid = (l + r) / 2;
            
            int left = min(1LL * (mid - 1) * k, 1LL * i);
            int right = min(1LL * mid * k - 1, 1LL * i);
            ll cost = query(left, right) + a[i + mid];
            if (cost <= 1LL * a[i] * (right - left + 1 + 1))
                l = mid + 1;
            else
                r = mid;
        }
        l--;
        if (l == 0)
            continue;

        int right = min(1LL * l * k - 1, 1LL * i);
        ll len = right + 1 + l;
        ll cost = len * a[i] - (query(0, right) + query(i + 1, i + l));
        ans = max(ans, pre[n - 1] + cost);
    }

    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

For every valid permutation we can always determine the index $$$k$$$ used as the split in the riffle shuffle operation, unless it is the sorted permutation.

Find the number of riffle shuffles for each split.

Lets prove Hint 1. For a valid permutation $$$q$$$, consider the first $$$k$$$ such that $$$k$$$ appers after $$$k + 1$$$ in $$$q$$$, if $$$q$$$ is a riffle shuffle of $$$[1, 2, \ldots, n]$$$ then we know that $$$k$$$ must be the split used. The only permutation where such a item does not exist is the one where the permutation is already sorted.

Now lets try finding the number of solutions for a specific split point $$$k$$$ in sub-quadratic time. We can think of it like this, colour all the numbers less than or equal to $$$k$$$ in blue and the elements bigger than $$$k$$$ in red. Now when we replace all $$$-1$$$ in $$$p$$$ the following must be true after, for each blue element $$$x$$$ exactly $$$x$$$ elements are blue in its prefix and for each red element $$$x$$$ exactly $$$x - k$$$ elements are red in its prefix. So now we just need to count the number of ways to insert red and blue elements so that this condition is satisfied. To find this iterate over each index that is not $$$-1$$$ and insert the number of elements of its colour that it demands and fill the remaining elements in its prefix with the other colour. This will have worst case $$$O(n)$$$ run time if we can calculate the required binomial coefficients in $$$O(1)$$$ which can be done by pre-calculating factorials.

So we can just iterate over each split and sum in $$$O(n^2)$$$ making sure to remember that we might overcount the sorted permutation.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

const int MOD = 998244353;

template<ll mod> // template was not stolen from https://mirror.codeforces.com/profile/SharpEdged
struct modnum {
    static constexpr bool is_big_mod = mod > numeric_limits<int>::max();

    using S = conditional_t<is_big_mod, ll, int>;
    using L = conditional_t<is_big_mod, __int128, ll>;

    S x;

    modnum() : x(0) {}
    modnum(ll _x) {
        _x %= static_cast<ll>(mod);
        if (_x < 0) { _x += mod; }
        x = _x;
    }

    modnum pow(ll n) const {
        modnum res = 1;
        modnum cur = *this;
        while (n > 0) {
            if (n & 1) res *= cur;
            cur *= cur;
            n /= 2;
        }
        return res;
    }
    modnum inv() const { return (*this).pow(mod-2); }
    
    modnum& operator+=(const modnum& a){
        x += a.x;
        if (x >= mod) x -= mod;
        return *this;
    }
    modnum& operator-=(const modnum& a){
        if (x < a.x) x += mod;
        x -= a.x;
        return *this;
    }
    modnum& operator*=(const modnum& a){
        x = static_cast<L>(x) * a.x % mod;
        return *this;
    }
    modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
    
    friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
    friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
    friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
    friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
    
    friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
    friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
    friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }

    friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
    friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
};

using mint = modnum<MOD>;

struct Combi{
    vector<mint> _fac, _ifac;
    int n;
    
    Combi() {
        n = 1;
        _fac.assign(n + 1, 1);
        _ifac.assign(n + 1, 1);
    }
    
    void check_size(int m){
        int need = n;
        while (need < m) need *= 2;
        m = need;
        if (m <= n) return;
        
        _fac.resize(m + 1);
        _ifac.resize(m + 1);
        for (int i = n + 1; i <= m; i++) _fac[i] = i * _fac[i - 1];
        
        _ifac[m] = _fac[m].inv();
        for (int i = m - 1; i > n; i--) _ifac[i] = _ifac[i + 1] * (i + 1);
        n = m;
    }
    
    mint fac(int m){
        check_size(m);
        return _fac[m];
    }
    
    mint ifac(int m){
        check_size(m);
        return _ifac[m];
    }
    
    mint ncr(int n, int r){
        if (n < r || r < 0) return 0;
        
        return fac(n) * ifac(n - r) * ifac(r);
    }
    
    mint npr(int n, int r){
        if (n < r || r < 0) return 0;
        
        return fac(n) * ifac(n - r);
    }
} comb;

void solve(){
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) {
        cin >> x;
        if (x != -1)
            x--;
    }

    mint ans = 0;

    for (int i = 0; i < n - 1; i++){
        mint res = 1;
        int spaces = 0;
        int less = -1;
        int more = i;
        for (int j = 0; j < n; j++){
            if (a[j] == -1){
                spaces++;
                continue;
            }

            if (a[j] <= i){
                int need = a[j] - less - 1;
                res *= comb.ncr(spaces, need);
                more += spaces - need;
                less = a[j];

            }

            if (a[j] > i){
                int need = a[j] - more - 1;
                res *= comb.ncr(spaces, need);
                less += spaces - need;
                more = a[j];
            }

            spaces = 0;
        }

        res *= comb.ncr(spaces, i - less);

        ans += res;
    }

    bool sorted = true;
    for (int i = 0; i < n; i++){
        if (a[i] != i && a[i] != -1)
            sorted = false;
    }

    if (sorted)
        ans -= n - 2;
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}

Solve the easy version.

If $$$p_i \lt i$$$ we know that $$$p_i$$$ must belong to the left side of the split, similarly if $$$p_i \gt i$$$ we know that $$$p_i$$$ must belong to the right side of the split.

If a permutation p is a riffle shuffle of $$$[1,2,\ldots,n]$$$, then it will have three regions described by two integers $$$l, r$$$ as follows:

• a prefix where for all $$$i$$$ ($$$1 \le i \le l$$$) we have $$$p_i = i$$$.

• a suffix where for all $$$i$$$ ($$$r \le i \le n$$$) we have $$$p_i = i$$$.

• a middle region where for all $$$i$$$ ($$$l \lt i \lt r$$$) we have $$$p_i \ne i$$$.

See that the first region will all belong to the left side of the split, and the last region will all belong to the right side of the split. Additionally, we can deduce the side of the entire middle region from Step 2. There is a single edge case to this where $$$p$$$ is the sorted permutation.

Suppose there is an index $$$i$$$ where $$$a_i \ne i$$$ and $$$a_i \ne -1$$$, or in other words, the sorted permutation is not valid. In this case, from Step 3, we can deduce the side of every element $$$i$$$ where $$$a_i \ne -1$$$.

For the opposite case to Step 4 (i.e, the case where the sorted permutation is valid), can you think of a way to solve this?

Now lets solve the same case as Step 4. For each $$$k$$$, consider a consecutive run of $$$-1$$$ and try to find the number of ways to fill it, lets try to find some nice properties for some cases. Let me introduce some notation, I will type each gap in the following way:

• an $$$l \rightarrow l$$$ gap means the element immediately before the gap belongs to the left side of the split and the element after belongs to the left side of the split.

• an $$$l \rightarrow r$$$ gap means the element immediately before the gap belongs to the left side of the split and the element after belongs to the right side of the split.

• similar notation for $$$r \rightarrow l$$$ and $$$r \rightarrow r$$$.

Now notice that for any $$$k$$$, the number of ways to fill an $$$l \rightarrow l$$$ or $$$r \rightarrow r$$$ gap will always be the same.

For the $$$l \rightarrow r$$$ and $$$r \rightarrow l$$$ gaps, we have to get a bit more creative. The key thing to notice is that each $$$k$$$ will demand a unique number of elements from the left side of the split to be placed inside the gap. Now since the number of left elements must be between $$$0$$$ and the size of the gap, we can restrict the number of $$$k$$$ we need to consider to no more than the size of the gap!

For each gap, calculate this range of valid $$$k$$$, and take the intersection of all the ranges. Now if we use a very similar implementation to the easy version of the problem but only consider $$$k$$$ within this range, and skipping $$$l \rightarrow l$$$ and $$$r \rightarrow r$$$ gaps by calculating their contribution separately, the problem will be solved. Since, say, the range of valid $$$k$$$ has size $$$x$$$, then the number of $$$l \rightarrow r$$$ and $$$r \rightarrow l$$$ gaps will be no more than approximately $$$n/x$$$, and so the final time complexity is $$$O(x \cdot n/x)$$$, which is $$$O(n)$$$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(x) cout << #x << " = " << x << "\n";
#define vdebug(a) cout << #a << " = "; for(auto x: a) cout << x << " "; cout << "\n";
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

const int MOD = 998244353;

template<ll mod> // template was not stolen from https://mirror.codeforces.com/profile/SharpEdged
struct modnum {
    static constexpr bool is_big_mod = mod > numeric_limits<int>::max();

    using S = conditional_t<is_big_mod, ll, int>;
    using L = conditional_t<is_big_mod, __int128, ll>;

    S x;

    modnum() : x(0) {}
    modnum(ll _x) {
        _x %= static_cast<ll>(mod);
        if (_x < 0) { _x += mod; }
        x = _x;
    }

    modnum pow(ll n) const {
        modnum res = 1;
        modnum cur = *this;
        while (n > 0) {
            if (n & 1) res *= cur;
            cur *= cur;
            n /= 2;
        }
        return res;
    }
    modnum inv() const { return (*this).pow(mod-2); }
    
    modnum& operator+=(const modnum& a){
        x += a.x;
        if (x >= mod) x -= mod;
        return *this;
    }
    modnum& operator-=(const modnum& a){
        if (x < a.x) x += mod;
        x -= a.x;
        return *this;
    }
    modnum& operator*=(const modnum& a){
        x = static_cast<L>(x) * a.x % mod;
        return *this;
    }
    modnum& operator/=(const modnum& a){ return *this *= a.inv(); }
    
    friend modnum operator+(const modnum& a, const modnum& b){ return modnum(a) += b; }
    friend modnum operator-(const modnum& a, const modnum& b){ return modnum(a) -= b; }
    friend modnum operator*(const modnum& a, const modnum& b){ return modnum(a) *= b; }
    friend modnum operator/(const modnum& a, const modnum& b){ return modnum(a) /= b; }
    
    friend bool operator==(const modnum& a, const modnum& b){ return a.x == b.x; }
    friend bool operator!=(const modnum& a, const modnum& b){ return a.x != b.x; }
    friend bool operator<(const modnum& a, const modnum& b){ return a.x < b.x; }

    friend ostream& operator<<(ostream& os, const modnum& a){ os << a.x; return os; }
    friend istream& operator>>(istream& is, modnum& a) { ll x; is >> x; a = modnum(x); return is; }
};

using mint = modnum<MOD>;

struct Combi{
    vector<mint> _fac, _ifac;
    int n;
    
    Combi() {
        n = 1;
        _fac.assign(n + 1, 1);
        _ifac.assign(n + 1, 1);
    }
    
    void check_size(int m){
        int need = n;
        while (need < m) need *= 2;
        m = need;
        if (m <= n) return;
        
        _fac.resize(m + 1);
        _ifac.resize(m + 1);
        for (int i = n + 1; i <= m; i++) _fac[i] = i * _fac[i - 1];
        
        _ifac[m] = _fac[m].inv();
        for (int i = m - 1; i > n; i--) _ifac[i] = _ifac[i + 1] * (i + 1);
        n = m;
    }
    
    mint fac(int m){
        check_size(m);
        return _fac[m];
    }
    
    mint ifac(int m){
        check_size(m);
        return _ifac[m];
    }
    
    mint ncr(int n, int r){
        if (n < r || r < 0) return 0;
        
        return fac(n) * ifac(n - r) * ifac(r);
    }
    
    mint npr(int n, int r){
        if (n < r || r < 0) return 0;
        
        return fac(n) * ifac(n - r);
    }
} comb;

void solve(){
    int n;
    cin >> n;

    vector<int> a(n);
    for (int &x : a) {
        cin >> x;
        if (x != -1)
            x--;
    }

    bool fixed = true;
    for (int i = 0; i < n; i++)
        if (a[i] != -1 && a[i] != i)
            fixed = false;

    if (fixed){ //case where all a[i] != -1 has a[i] = i
        vector<mint> prod(n + 1);
        prod[0] = 1;
        for (int i = 1; i <= n; i++)
            prod[i] = prod[i - 1] * 2;

        int last = -1;
        mint ans = 0;
        for (int i = 0; i <= n; i++){
            if (i == n || a[i] != -1){
                int len = i - last - 1;
                ans += prod[len] - len - 1;
                last = i;
            }
        }

        ans += 1;
        cout << ans << "\n";
        return;
    }

    vector<bool> side(n);
    bool found = false;
    for (int i = 0; i < n; i++){
        if (a[i] == -1)
            continue;

        if (a[i] < i)
            side[i] = false; // left side
        if (a[i] > i)
            side[i] = true; // right side
        if (a[i] == i)
            side[i] = found;
        if (a[i] != i)
            found = true;
    }

    int last = -1;
    vector<array<int, 2>> ranges;
    for (int i = 0; i < n; i++){
        if (a[i] == -1)
            continue;
        
        if (last == -1){
            last = i;
            continue;
        }

        if (side[i] && !side[last]){ // left -> right gap
            int mn = last - a[last]; // min right already placed
            int mx = mn + i - last; // max right already placed
            ranges.push_back({a[i] - mx, a[i] - mn + 1});
        }

        if (!side[i] && side[last]){ // right -> left gap
            int mx = i - a[i]; // max right placed by last
            int mn = mx - (i - last); // min right placed by last
            ranges.push_back({a[last] - mx, a[last] - mn + 1});
        }

        last = i;
    }

    int l = 0, r = n - 1;
    for (auto [u, v] : ranges){
        l = max(l, u);
        r = min(r, v);
    }

    mint coef = 1;
    vector<mint> score(n); // score[i] = contribution when splitting at i
    for (int i = l; i <= r; i++)
        score[i] = 1;

    last = -1;
    for (int i = 0; i < n; i++){
        if (a[i] == -1)
            continue;
        
        bool prev = false;
        if (last != -1)
            prev = side[last];
        int spaces = i - last - 1;

        if (side[i] && prev || !side[i] && !prev){
            int cnt = 0;
            if (last == -1)
                cnt = a[i];
            else
                cnt = a[i] - a[last] - 1;

            coef *= comb.ncr(spaces, cnt);
        }

        if (side[i] && !prev){ // left -> right
            for (int j = l; j <= r; j++){
                int placed = 0;
                if (last != -1)
                    placed = last - a[last]; // how many right i have placed by last

                int need = a[i] - (j + placed); // j + placed is the next one i need to place after last
                score[j] *= comb.ncr(spaces, need);
            }
        }

        if (!side[i] && prev){ // right -> left
            for (int j = l; j <= r; j++){
                int big = i - a[i] + j - 1; // last right to be placed by i
                
                int need = big - a[last];
                score[j] *= comb.ncr(spaces, need);
            }
        }

        last = i;
    }

    for (int j = l; j <= r; j++){
        if (!side[last]){
            score[j] *= comb.ncr(n - last - 1, j - a[last] - 1);
        }
        else{
            score[j] *= comb.ncr(n - last - 1, n - 1 - a[last]);
        }
    }

    mint ans = 0;
    for (int i = 0; i < n; i++)
        ans += score[i];
    ans *= coef;
    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin >> t;
    while (t--) solve();
}