旅行
题目描述
假日在即,班上的 n 位同学正在讨论各自的旅行计划。
已知有 109 个景区,编号为 1∼109。同学编号为 1∼n,每位同学都有一个不喜欢的景区,编号为 i 的同学不喜欢的景区编号为 ci。
每位同学都需要说出自己的旅行计划。你需要为同学们制定一个发言顺序,用一个 1∼n 的排列 p 表示,代表编号为 p1,p2,⋯,pn 的同学依次发言。
每位同学会在前面同学发言结束后决定自己前往的景区。第 i 次发言时,编号为 pi 的同学会如下决定自己前往的景区 ti:
- 设置集合 S={cpi,t1,t2,⋯,ti−1},则 ti 是编号最小的不在 S 中的景区。
- 换而言之,就是 cpi 以外的编号最小的没有作为之前同学目的地的景区。
给定两个长度为 n 的非负整数数组 a,b,定义这种发言顺序 p 的权值为 ∏i=1n(aiti+bi),即所有 (aiti+bi) 的乘积。
可以发现总共有 n! 种不同的发言顺序,你需要求出所有发言顺序的权值总和。答案对 998244353 取模。
输入格式
第一行包含一个正整数 n,表示同学数量。
第二行 n 个正整数,第 i 个整数为 ci,表示编号为 i 的同学不喜欢的景区。
第三行 n 个非负整数,第 i 个整数为 ai,表示计算权值的系数。
第四行 n 个非负整数,第 i 个整数为 bi,表示计算权值的系数。
输出格式
输出一行一个非负整数,表示答案对 998244353 取模后的结果。
样例 1 输入
3
1 2 3
1 1 1
0 0 0
样例 1 输出
40
样例 2 输入
5
1 1 2 3 4
1 1 1 1 1
1 2 3 4 5
样例 2 输出
494088
样例 3 输入
6
1 1 4 5 6 6
2 4 2 9 3 1
2 0 9 3 8 4
样例 3 输出
164404605
样例解释 1
共有 6 种不同的发言顺序:
- p=[1,2,3],此时 t=[2,1,4],权值为 2×1×4=8;
- p=[1,3,2],此时 t=[2,1,3],权值为 2×1×3=6;
- p=[2,1,3],此时 t=[1,2,4],权值为 1×2×4=8;
- p=[2,3,1],此时 t=[1,2,3],权值为 1×2×3=6;
- p=[3,1,2],此时 t=[1,2,3],权值为 1×2×3=6;
- p=[3,2,1],此时 t=[1,3,2],权值为 1×3×2=6;
故答案为 8+6+8+6+6+6=40。
样例 4
见选手目录下的 travel4.in 与 travel4.ans。
样例 5
见选手目录下的 travel5.in 与 travel5.ans。
样例 6
见选手目录下的 travel6.in 与 travel6.ans。
样例 7
见选手目录下的 travel7.in 与 travel7.ans。
样例 8
见选手目录下的 travel8.in 与 travel8.ans。
样例 9
见选手目录下的 travel9.in 与 travel9.ans。
样例 10
见选手目录下的 travel10.in 与 travel10.ans。
数据范围
对于所有测试数据,保证:1≤n≤5000,1≤ci≤109,0≤ai,bi<998244353。
| 测试点编号 |
n≤ |
特殊性质 |
| 1,2 |
10 |
无 |
| 3∼5 |
16 |
| 6,7 |
5000 |
A |
| 8,9 |
300 |
B |
| 10,11 |
^ |
C |
| 12,13 |
D |
| 14,15 |
无 |
| 16∼20 |
5000 |
^ |
- 特殊性质 A:ai=1,bi=0;
- 特殊性质 B:n 为偶数,且 ci∈{1,n/2};
- 特殊性质 C:ci 互不相同;
- 特殊性质 D:不存在 i<j<k 满足 ci=cj=ck。