O - Pair Score
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 6 点
問題文
1 から N の番号がついた N 人の人がいます。人 i は整数 B_i が書かれたゼッケンをつけています。
この N 人を横一列に並べる方法は N! 通りありますが、各並びについて、以下で定めるスコアを求め、その総和を 998244353 で割った余りを求めてください。
- 左から i 番目の人のゼッケンにかかれている整数を A_i とする。f(i,j) を、A_j-A_i=j-i であるとき S_{j-i}、それ以外のとき 0 とする。1\leq i < j \leq N を満たす全ての組 (i,j) についての f(i,j) の総和をスコアとする
制約
- 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=(2,3,1) となり、スコアは f(1,2)+f(1,3)+f(2,3)=1+0+0=1
- 左から人 2,3,1 と並べたとき、A=(2,1,3) となり、スコアは f(1,2)+f(1,3)+f(2,3)=0+0+0=0
- 左から人 3,1,2 と並べたとき、A=(1,3,2) となり、スコアは f(1,2)+f(1,3)+f(2,3)=0+0+0=0
- 左から人 3,2,1 と並べたとき、A=(1,2,3) となり、スコアは 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 で割った余りを求めてください。
Score : 6 points
Problem Statement
There are N people numbered 1 to N. Person i wears an integer B_i.
There are N! ways to make them stand in a row from left to right. The score for each of these ways is defined as follows. Find the sum of all those scores, modulo 998244353.
- Let A_i denote the integer worn by the i-th person from the left. Let f(i,j) be S_{j-i} if A_j-A_i=j-i and 0 otherwise. The score is the sum of f(i,j) over all pairs (i,j) such that 1\leq i < j \leq N.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq B_i \leq 10^5
- 1 \leq S_i \leq 998244352
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N B_1 \ldots B_N S_1 \ldots S_N
Output
Print the answer.
Sample Input 1
3 3 2 1 1 10 100
Sample Output 1
14
- When arranging them in the order 1, 2, 3 from left to right, we have A=(3,2,1), for a score of f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
- When arranging them in the order 1, 3, 2 from left to right, we have A=(3,1,2), for a score of f(1,2)+f(1,3)+f(2,3)=0+0+1=1.
- When arranging them in the order 2, 1, 3 from left to right, we have A=(3,1,2), for a score of f(1,2)+f(1,3)+f(2,3)=1+0+0=1.
- When arranging them in the order 2, 3, 1 from left to right, we have A=(3,1,2), for a score of f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
- When arranging them in the order 3, 1, 2 from left to right, we have A=(3,1,2), for a score of f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
- When arranging them in the order 3, 2, 1 from left to right, we have A=(3,1,2), for a score of f(1,2)+f(1,3)+f(2,3)=1+10+1=12.
Therefore, the answer is 0+1+1+0+0+12=14.
Sample Input 2
3 3 3 1 1 10 100
Sample Output 2
20
- When arranging them in the order 1, 2, 3 from left to right, we have A=(3,3,1), for a score of f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
- When arranging them in the order 1, 3, 2 from left to right, we have A=(3,1,3), for a score of f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
- When arranging them in the order 2, 1, 3 from left to right, we have A=(3,3,1), for a score of f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
- When arranging them in the order 2, 3, 1 from left to right, we have A=(3,1,3), for a score of f(1,2)+f(1,3)+f(2,3)=0+0+0=0.
- When arranging them in the order 3, 1, 2 from left to right, we have A=(1,3,3), for a score of f(1,2)+f(1,3)+f(2,3)=0+10+0=10.
- When arranging them in the order 3, 2, 1 from left to right, we have A=(1,3,3), for a score of f(1,2)+f(1,3)+f(2,3)=0+10+0=10.
Therefore, the answer is 0+0+0+0+10+10=20.
Sample Input 3
9 3 1 4 15 9 2 6 5 35 1 12 123 1234 12345 123456 1234567 12345678 123456789
Sample Output 3
146471953
Be sure to find it modulo 998244353.