Description

\(\mathcal{P}{\rm ortal.}\)

Solution

After reading the prompt, we found that each number must go to the target direction when switching. Therefore, if there is a number, it must be illegal to have a larger number in front of it and a smaller number behind it, that is, it is required that there is no descending subsequence with a length of more than \ (2\).

According to the \ (\textrm{dilworth}\) theorem, the length of the longest descending subsequence does not exceed \ (2\), that is, the number of ascending subsequences whose whole arrangement is divided into \ (2\) at least cannot exceed \ (2\)

Regardless of the dictionary order restriction, note that \ (f(i,j) \) is the maximum number of the first \ (i\) and the following \ (n-i\) positions are legal schemes (note that only the schemes at the following positions are calculated). Consider the number of \ (i+1\). If \ (k>j\) is filled, it must be legal; If \ (k<j\) is filled, the minimum value (\rm val\) that has not been filled must be filled. Otherwise, the sequence will appear \ (j>k>\rm val\) like objects, and the number of ascending subsequences must exceed \ (2\). So there is \ (f(i,j)\leftarrow \sum_{k=j}^{n}f(i+1,k)\).

In fact, this recursion can be represented by images

For the case of \ (n=7\) and solving \ (f(1,1) \), it is actually the number of schemes starting from \ (A\) to \ (B\) and not to \ (y=x-1\). First, consider the case that there is no straight-line limit. In fact, it is A total of \ (n-i\) times, one step to the right each time, and \ (x(x\geqslant 0) \) steps upward, and \ (n-j=\sum x\). The number of schemes can be calculated as \ (\binom{2n-i-j-1}{n-i-1}\) by using the board inserting method

In fact, this is very similar to the Cartland number. Poor \ (\require{enclosure}\enclosure{horizontalstrike}{\sf{oxide}} \) has been stuck in this place for a long time. It seems that this is a model in which one operation includes "one step to the right every time, and one step up \ (x(x\geqslant 0) \)". In fact, it can be found from drawing that since \ (x\) can be equal to zero, its number of schemes is equivalent to that of "one step to the right every time, the first step must be to the right"! From this point of view, we can also understand why the unlimited number of schemes is \ (\binom{2n-i-j-1}{n-i-1} \), because the first step is fixed.

Now consider adding restrictions. Imitating the derivation of Cartland number, we directly symmetrically ((n,n) \) along \ (y=x-1\) to \ ((n+1,n-1) \), and then calculate the number of schemes starting from \ ((i,j) \), the first step is to go right to \ ((n+1,n-1) \)? In fact, there is a problem. When you go to \ (y=x-1\) for the first time, this calculation will include the next step of going up \ (x (x>0) \). Since the original operation is a combination of going right and going up, this point does not actually go to \ (y= x-1\). How to solve it? Force the first time you go to \ (y=x-1\), you can go one step to the right. Then you can find that this is the straight line to \ (y=x-2\), so the number of illegal schemes starts from \ ((i,j) \), and the first step is to go right to the number of schemes to \ ((n+2,n-2) \), that is, \ (\binom{2n-i-j-1}{n-i+1}\)

Continue to consider dictionary order constraints. Enumeration by bit. If the current enumeration reaches the \ (i\) item, it is the number of schemes where the \ (i-1\) item is the same as \ (\{q\}\) before calculation, and the \ (i\) item is greater than \ (q\u i\).

Mark \ (\lim=\max\u{j=1}^{i-1}q\u j\), \ ({\rm val}\) is the minimum value that has not been filled in at present. Since \ ({\rm val}\) is the minimum value that has not been filled in at present, \ (q\u i\geqslant \rm val\) cannot be filled in, \ (\rm val\). Take \ (\max\) from \ (\q\u i\) and \ (\lim\) and write the answer as \ (r\), then the number of schemes is \ (\sum\u{k=r+1}^n f (I, K) \), which is \ (i-1, r+1) \). According to the above derivation, it can be calculated with the combination number \ (\mathcal O(1) \). So the total complexity is \ (\mathcal O(nT) \)

Another thing to note about the dictionary order is that since the \ (i-1\) item is the same as \ (\{q\}\) before the imperial order, in order to maintain the condition that "the number of ascending subsequences divided into \ (2\) at least cannot exceed \ (2\)", it is not enough to only ensure that \ (\rm val\) or \ (k>\rm lim\) is selected. Considering that if \ ({\rm val}<q\u i<\lim\) occurs, a subsequence of \ (\lim, q\u I, {\rm val}\} \) will be generated. From \ (i+1\), all schemes cannot be legal.

Code

# include <cstdio>
# include <cctype>
# define print(x,y) write(x), putchar(y)

template <class T>
inline T read(const T sample) {
    T x=0; char s; bool f=0;
    while(!isdigit(s=getchar())) f|=(s=='-');
    for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
    return f? -x: x;
}
template <class T>
inline void write(T x) {
    static int writ[50], w_tp=0;
    if(x<0) putchar('-'), x=-x;
    do writ[++w_tp]=x-x/10*10, x/=10; while(x);
    while(putchar(writ[w_tp--]^48), w_tp);
}

# include <cstring>
# include <iostream>
using namespace std;

const int maxn = 1200005;
const int mod = 998244353;

int inv(int x,int y=mod-2,int r=1) {
    for(; y; y>>=1, x=1ll*x*x%mod)
        if(y&1) r=1ll*r*x%mod; return r;
}
int dec(int x,int y) { return x-y<0?x-y+mod:x-y; }
int inc(int x,int y) { return x+y>=mod?x+y-mod:x+y; }

bool vis[maxn];
int n,fac[maxn],ifac[maxn];

void initialize() { fac[0]=1;
    for(int i=1;i<=maxn-5;++i)
        fac[i] = 1ll*fac[i-1]*i%mod;
    ifac[maxn-5] = inv(fac[maxn-5]);
    for(int i=maxn-6;i>=0;--i)
        ifac[i] = 1ll*ifac[i+1]*(i+1)%mod;
}

int C(int n,int m) {
    if(m<0 || n<m) return 0;
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

int f(int i,int j) { return dec(
    C(n*2-i-j-1,n-i-1), C(n*2-i-j-1,n-i+1)
); }

void CandyMyWife() {
    bool judge = false;
    n=read(9); int lim=0, ans=0, val=1;
    memset(vis,0,sizeof(bool)*(n+2));
    for(int i=1;i<=n;++i) {
        int x=read(9); if(judge) continue;
        ans = inc(ans,f(i-1,max(lim,x)+1));
        if(val<x && x<lim) judge = true;
        lim = max(lim,x); vis[x] = true;
        while(vis[val]) ++ val;
    } print(ans,'\n');
}

int main() {
    initialize();
    for(int T=read(9); T; --T) CandyMyWife();
    return 0;
}