← 返回题目列表

AtCoder · past202112_o

O. 配对分数

中文机器翻译题面 查看原题

分数: 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.