AT_arc169_f.[ARC169F] Large DP Table

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_N)$ 、 $B=(B_1,B_2,\cdots,B_N)$ 、 $X=(X_1,X_2,\cdots,X_N)$ 、 $Y=(Y_1,Y_2,\cdots,Y_N)$ 。其中， $A$ 和 $B$ 满足以下性质：

$A_1=1$ 。
$B_1=2$ 。
$(A_1,A_2,\cdots,A_N,B_1,B_2,\cdots,B_N)$ 是 $(1,2,\cdots,2N)$ 的一个排列。

定义整数 $d_{i,j}$ （ $1\leq i,j\leq N$ ）如下：

$d_{1,1}=0$ 。
当 $(i,j)\neq (1,1)$ 且 $A_i < B_j$ 时： $d_{i,j}=d_{i,j-1}+X_i$ 。
当 $(i,j)\neq (1,1)$ 且 $A_i > B_j$ 时： $d_{i,j}=d_{i-1,j}+Y_j$ 。

请计算 $\sum_{1\leq i\leq N}\sum_{1\leq j\leq N}d_{i,j}$ ，并输出其对 $998244353$ 取模的结果。

输入格式

输入通过标准输入给出，格式如下：

$N$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_N$ $X_1$ $X_2$ $\cdots$ $X_N$ $Y_1$ $Y_2$ $\cdots$ $Y_N$

输出格式

输出答案。

输入输出样例

输入#1
```
2
1 4
2 3
2 2
1 3
```
输出#1
```
8
```

输入#2

3
1 3 5
2 6 4
1 10 100
1000 10000 100000

输出#2

输入#3

3
1 6 5
2 4 3
1 10 100
1000 10000 100000

输出#3

输入#4

10
1 17 4 7 16 18 9 3 12 6
2 19 20 14 5 11 13 8 15 10
744280520 249168130 239276621 320064892 910500852 164832983 245532751 198319687 715892722 967824729
769431650 80707350 459924868 257261830 777045524 583882654 950300099 438099970 322288793 532405020

输出#4

746075419

说明/提示

限制条件

$2\leq N\leq 250000$ 。
$A_1=1$ 。
$B_1=2$ 。
$(A_1,A_2,\cdots,A_N,B_1,B_2,\cdots,B_N)$ 是 $(1,2,\cdots,2N)$ 的一个排列。
$1\leq X_i\leq 10^9$ 。
$1\leq Y_i\leq 10^9$ 。
输入的所有值均为整数。

样例解释 1

$d_{i,j}$ 的值如下：

$d_{1,1}=0$
$d_{1,2}=d_{1,1}+X_1=0+2=2$
$d_{2,1}=d_{1,1}+Y_1=0+1=1$
$d_{2,2}=d_{1,2}+Y_2=2+3=5$

因此，所求答案为 $0+2+1+5=8$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页