QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 5408. 计数鸡

统计

小 C 是一名计算机系的学生。这学期他选了 H 老师的计算概论课。

这一门课期中没有考试,取而代之的是一次期中大作业,作业内容如下:

H 老师给定了个 $1$ 到 $n$ 的排列 $q_1, q_2, \cdots, q_n$。以及额外的一个仅包含整数的长度为 $n$ 的数组 $h_1, h_2, \cdots, h_n$。

H 老师认为一个 $1$ 到 $n$ 的排列 $p$ 的优美度 $val$ 为 $\displaystyle \sum_{i=1}^n \sum_{j=i+1}^n [p_i \geq p_j]+[(p_i + h_i) \geq q_j]$。

小 C 需要计算出来有多少个排列,满足其优美度为偶数。由于答案很大,只需要提交答案对 $998\,244\,353$ 取模后的校验值即可。

小 C 觉得老师在欺负他这个学了 $3$ 个月计算机的小萌新,于是只能找到在这里集训的你,帮他解决这个问题。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个用空格隔开的正整数,其中第 $i$ 个数是 $q_i$。

第三行 $n$ 个用空格隔开的整数,其中第 $i$ 个数是 $h_i$。

输出格式

一行一个整数,表示优美度为偶数的排列 $P$ 的个数对 $998\,244\,353$ 取模的结果。

样例数据

样例输入

3
2 1 3
0 0 0

样例输出

3

样例解释

1 2 3 的优美度为 $1$。

1 3 2 的优美度为 $3$。

2 1 3 的优美度为 $2$。

2 3 1 的优美度为 $4$。

3 1 2 的优美度为 $4$。

3 2 1 的优美度为 $5$。

子任务

  • Subtask 1[20 分]:$n \leq 20$。
  • Subtask 2[30 分]:$h_i = 0$。
  • Subtask 3[50 分]:没有额外的限制。

对于所有测试数据,保证 $1 \leq n \leq 300$,$-n \leq h_i \leq n$,$q_i$ 是一个 $1 \sim n$ 的排列。