#1750. 计数鸡

    ID: 1750 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1091来源:qoj.ac数据:公开样例枚举组合数学

计数鸡

计数鸡

题目描述

标题: 计数鸡 - Problem - QOJ.ac

#5408. 计数鸡

Statistics

The problem was used in the following contests:

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

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

H 老师给定了个 1 到 n 的排列 q1,q2,⋯,qn。以及额外的一个仅包含整数的长度为 n 的数组 h1,h2,⋯,hn。

H 老师认为一个 1 到 n 的排列 p 的优美度 val 为 ∑i=1n∑j=i+1n[pi≥pj]+[(pi+hi)≥qj]。

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

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

输入格式

第一行一个正整数 n。

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

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

输出格式

一行一个整数,表示优美度为偶数的排列 P 的个数对 998244353 取模的结果。

样例数据

样例输入

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≤20。
  • Subtask 2[30 分]:hi=0。
  • Subtask 3[50 分]:没有额外的限制。

对于所有测试数据,保证 1≤n≤300,−n≤hi≤n,qi 是一个 1∼n 的排列。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
2 1 3
0 0 0
3