分数: 6 点
问题陈述
有 N 人数 1 to N。人 i 佩戴一个整数 B_i.
有 N! 让他们从左到右站成一排的方法。每种方式的分数定义如下。求所有这些分数的总和,取模 998244353.
- 让 A_i 表示佩戴的整数 i左起第一个人。让 f(i,j) be S_{j-i} if A_j-A_i=j-i 和 0 否则。分数是以下总和 f(i,j) 所有对 (i,j) 这样 1\leq i < j \leq N.
约束
- 2 \leq N \leq 10^5
- 1 \leq B_i \leq 10^5
- 1 \leq S_i \leq 998244352
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N B_1 \ldots B_N S_1 \ldots S_N
输出
打印答案。
示例输入 1
3 3 2 1 1 10 100
示例输出 1
14
- 按顺序排列时 1, 2, 3 从左到右,我们有 A=(3,2,1),得分为 f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
- 按顺序排列时 1, 3, 2 从左到右,我们有 A=(3,1,2),得分为 f(1,2)+f(1,3)+f(2,3)=0+0+1=1.
- 按顺序排列时 2, 1, 3 从左到右,我们有 A=(3,1,2),得分为 f(1,2)+f(1,3)+f(2,3)=1+0+0=1.
- 按顺序排列时 2, 3, 1 从左到右,我们有 A=(3,1,2),得分为 f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
- 按顺序排列时 3, 1, 2 从左到右,我们有 A=(3,1,2),得分为 f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
- 按顺序排列时 3, 2, 1 从左到右,我们有 A=(3,1,2),得分为 f(1,2)+f(1,3)+f(2,3)=1+10+1=12.
因此,答案是 0+1+1+0+0+12=14.
示例输入 2
3 3 3 1 1 10 100
示例输出 2
20
- 按顺序排列时 1, 2, 3 从左到右,我们有 A=(3,3,1),得分为 f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
- 按顺序排列时 1, 3, 2 从左到右,我们有 A=(3,1,3),得分为 f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
- 按顺序排列时 2, 1, 3 从左到右,我们有 A=(3,3,1),得分为 f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
- 按顺序排列时 2, 3, 1 从左到右,我们有 A=(3,1,3),得分为 f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
- 按顺序排列时 3, 1, 2 从左到右,我们有 A=(1,3,3),得分为 f(1,2)+f(1,3)+f(2,3)=0+10+0=10.
- 按顺序排列时 3, 2, 1 从左到右,我们有 A=(1,3,3),得分为 f(1,2)+f(1,3)+f(2,3)=0+10+0=10.
因此,答案是 0+0+0+0+10+10=20.
示例输入 3
9 3 1 4 15 9 2 6 5 35 1 12 123 1234 12345 123456 1234567 12345678 123456789
示例输出 3
146471953
一定要找到它的模 998244353.