神(du)仙(liu)题

首先研究一下题目: 要求\max – \min \le n-1.

而对于任意集合, 都有\max – \min \ge n-1 (等号成立需满足集合元素连续)

  • 故, 题意转化为求有多少的排列p满足以i为右端点的最大连续区间长度为a_i.

sol

显然, 最大连续区间不满足单调性.

那么先介绍几个与题目有关的性质:

  • \text{Theorem 1:}

    两个最长连续区间a,b要么包含, 要么不交.

  • \text{Theorem 2:}

    a_n=n

证略. 以上2个是简单但却有用的引理

我们判断无解直接利用这2条性质就好了.

根据引理1, 我们将每个最长连续区间抽象成一个点, 且连向包含它的最小区间.

这样会形成一个树形结构, 我们就可以在这颗树上求解.


f_n表示序列长度为n+1\lbrace a_n\rbrace =\lbrace 1,1,\dots1,n+1\rbrace的情况下的方案数,

且用ans_u表示树上u节点规模的方案数, 那么答案就是ans_n ([1,n]).

进一步的, 二者的联系为:

ans_u=f_{sz_u} \cdot \prod_{v \in \text{son of u}} ans_v

下面给出该式子的证明:

Proof

考虑ans_u要干什么:

  1. 保证孩子节点满足引理1的情形下给它们”分配数字”.

    即不会出现分配数字后, 实际的最长连续区间会有交.

  2. 递归子节点规模的答案.

难点在\text{step1}, 由于孩子节点的区间是不交的.

故, 只要确定区间之间的相对顺序(在引理1前提下!)就可以分配数字了.

且如果相对顺序确定, 每个子节点分配哪些数字都是确定的

而上述要求恰就是f_{sz_u}.


关于f的递推式, 网上伪证繁多, 且光讨论此题的递推式意义不大

再说, 可以直接\text{oeis}.

所以直接给出递推式:

f(n)=(n-1) f(n-1)+\sum_{i=2}^{n-2}(n-i-1) f(i) f(n-i)\\ f(0)=1, f(1)=2

代码实现

背景问题:

f(n)=\sum_{i=1} ^{n-1} f(i)f(n-i)

怎么求呢?

发现一般的分治fft不好求f*f形式的卷积.

为什么?

\text{cdq}分治本质上在做[l,mid]*[1,r-l]

  • l=1时: [1,mid]会卷上[1,r-1]

    [1,r-1]显然是会出现>mid的元素, 即未求解出来的情况.

  • l\neq 1时却不会: 考虑分治过程会形成一颗类似线段树结构

    那么[1,r-l]f显然是已经求解完的.

故, 我们需要将\text{case 1}的贡献保留.

操作步骤如下:

  1. l=1则令[l,mid] * [l,mid]并做贡献.
  2. l\neq 1则令[l,mid]*[1, r-l]并将该贡献乘以2.

感性理解, 这是对的

考虑l=1时, 将不方便做贡献的[1,mid]*[mid+1,r-l]先不做贡献.

那么由于f这个递推式具有对称性, 即f(i)\cdot f(n-i)=f(n-i)\cdot f(i)

故只要将\text{case 2}的情况乘以2就弥补回之前的少的贡献了.

个人建议手摸一遍 (认真脸

upd:
根据zzd的指示, 其实可以推广到更广… 可能我一直没仔细研究吧.
也就是说这样的卷积形式也是可以的:

f(n) = \sum_{i = 1} ^ {n – 1} f(i) g(i)f(n – i)

咋做?

  1. l=1则令[l,mid] * [l,mid]并做贡献.
  2. l\neq 1
    • 则令[l,mid]*[1, r-l]并做贡献.
    • 还有[1, r – l] * [l, mid]部分的

注意, 这里的卷积a*b是有序的, 即a部分为 f(i)\cdot g(i), b部分为f(n-i).
显然也是对的


回到本题, 可以将其他边角部分加加减减, 就变成要求:

f(n)=\sum_{i=1}^{n-1}(n-i-1) f(i) f(n-i)

进一步的, 考虑2\cdot f(n)

\begin{aligned} 2f(n)&=2\cdot \sum_{i=1}^{n-1}(n-i-1) f(i) f(n-i)\\ &= \sum_{i=1}^{n-1} \Big( (n-i+1) + (i-1)\Big) f(i)f(n-i)\\ &=\sum_{i=1} ^{n-1} (n-2) f(i) f(n-i) \end{aligned}

那么系数是只跟n有关的, 就转变成立上面例子的东东了.

然后对于每个询问可以用单调栈维护出来.

总复杂度O(n\log^2n+T\cdot n)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 1 << 17 | 5;
const int mod = 998244353, i2 = mod + 1 >> 1;

inline void read(int &x) {
  x = 0; char c = getchar();
  for(; !isdigit(c); c = getchar());
  for(;  isdigit(c); c = getchar())
    x = x * 10 + c - '0';
}
inline void upd(int &u, int v) {
  u += v; if(u >= mod) u -= mod;
}
inline int add(int u, int v) {
  return u + v < mod ? u + v : u + v - mod;
}
inline int sub(int u, int v) {
  return u - v < 0 ? u - v + mod : u - v;
}
inline int mul(int u, int v) {
  return (LL) u * v % mod;
}
inline int Pow(int a, int b = mod - 2) {
  int res = 1;
  for(; b; b >>= 1, a = mul(a, a))
    if(b & 1) res = mul(res, a);
  return res;
}

int cas, n, a[N], s[N];
namespace sol {
  int n, lim, rev[N], o[N], a[N], b[N], f[N];

  inline void init(int n) {
    for(lim = 1; lim < n; lim <<= 1);
    for(int i = 0; i < lim; ++i)
      rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0);
    for(int i = 0; i < lim >> 1; ++i) {
      int c = (mod - 1) / lim * i;
      o[i] = Pow(3, c);
    }
  }

  void Dft(int *a) {
    static int t;
    for(int i = 0; i < lim; ++i)
      if(i < rev[i]) swap(a[i], a[rev[i]]);
    for(int m = 1, tmp = lim >> 1; m < lim; m <<= 1, tmp >>= 1) 
      for(int i = 0; i < lim; i += m << 1) {
    int *l = a + i, *r = l + m;
    for(int k = 0; k < m; ++k) {
      t = mul(r[k], o[tmp * k]);
      r[k] = sub(l[k], t);
      l[k] = add(l[k], t);
    } 
      }     
  }
  void Idft(int *a) {
    reverse(a + 1, a + lim);
    Dft(a);
    int iv = Pow(lim);
    for(int i = 0; i < lim; ++i)
      a[i] = mul(a[i], iv);
  }
  void calc(int l, int mid, int r) {
    int n, m;
    if(l == 1) n = mid - l + 1, m = n + 1;
    else n = mid - l + 1, m = r - l + 1;
    init(n + m - 1);
    for(int i = 0; i < lim; ++i)
      a[i] = b[i] = 0;
    for(int i = 0; i < n; ++i) a[i] = f[i + l];
    for(int i = 1; i < m; ++i) b[i] = f[i];
    Dft(a), Dft(b);
    for(int i = 0; i < lim; ++i) 
      a[i] = mul(a[i], b[i]);
    if(l - 1)
      for(int i = 0; i < lim; ++i)
    a[i] = mul(a[i], 2);
    Idft(a);
    for(int i = mid + 1; i <= r; ++i) 
      upd(f[i], a[i - l]);
  }
  void solve(int l, int r) {
    if(l == r) {
      if(l == 1) return ;
      f[r] = mul(f[r], r - 2);
      f[r] = mul(f[r], i2);
      f[r] = sub(f[r], mul(2 * (r - 2), f[r - 1]));
      f[r] = add(f[r], mul(r - 1, f[r - 1]));
      return ;
    }
    int mid = l + r >> 1;
    solve(l, mid);
    calc(l, mid, r);
    solve(mid + 1, r);
  }

  void main() {
    f[0] = 1, f[1] = 2;
    solve(1, 50000);
  }    
}

inline bool jud() {
  if(a[n] != n) return 0;
  static int l[N], r[N], st[N], top, cnt;
  top = 0;
  for(int i = 1; i <= n; ++i) {
    if(a[i] > i) return 0;
    cnt = 0;
    l[i] = i - a[i] + 1, r[i] = i;
    while(top) {
      if(l[st[top]] < l[i] && st[top] >= l[i]) 
    return 0;
     if(l[st[top]] >= l[i])
    ++cnt, --top;
     else break;
    }
    s[i] = cnt;
    st[++top] = i;
  } return 1;
}
int main() {
  sol :: main();
  for(cin >> cas >> n; cas--;) {
    int ans = 1;
    for(int i = 1; i <= n; ++i)
      read(a[i]);
    if(!jud()) {
      printf("0\n");
      continue;
    }
    for(int i = 1; i <= n; ++i) 
      ans = mul(ans, sol :: f[s[i]]);
    printf("%d\n", ans);
  }
  return 0;
}