# 占卜## 题目背景LHY 擅长使用卡牌进行占卜。## 题目描述LHY 在占卜的时候会提前准备两套数字卡牌每套有 $n$ 张。每次占卜 LHY 会先从第一套卡牌中抽取若干张至少一张称为先验结果；然后从第二套卡牌中抽取若干张至少一张称为后验结果。然后 LHY 会进行降神仪式仪式中每次操作可以将先验结果或后验结果中的一张牌的数值 $+1$。如果可以通过最少 $x$ 次操作使得先验结果与后验结果相同即

解题思路

首先，我们可以将先验结果和后验结果的卡牌数值统计出来，得到两个数组$A$和$B$，其中$A[i]$表示第一套卡牌中数值为$i$的卡牌的数量，$B[i]$表示第二套卡牌中数值为$i$的卡牌的数量。

接下来，我们考虑如何计算可信度。假设我们进行了$x$次操作，将先验结果中的某个数值加1，那么相当于将$A[i]$减1，并将$A[i+1]$加1。如果我们能够通过$x$次操作使得先验结果和后验结果相同，那么必然有：

$A[1] = B[1]$ $A[2] = B[2]$ ... $A[m] = B[m]$

其中$m$是两个数组中非零元素的最大值。

现在的问题就是求解$x$的最小值。我们可以从后向前遍历这两个数组，对于每一个位置$i$，我们都需要通过一定次数的操作来将$A[i]$变为$B[i]$。

具体地，如果$A[i] < B[i]$，那么我们需要进行$B[i] - A[i]$次操作，将$A[i]$加到$B[i]$的数量。而如果$A[i] > B[i]$，那么我们需要将$A[i]$减少到$B[i]$的数量，这时我们需要考虑将$A[i]$中的数值“向后移动”。假设$A[i]$的当前数量为$a$，$B[i]$的当前数量为$b$，而我们需要将$A[i]$减少到$b$的数量。那么我们可以将$A[i]$中的$a-b$个数值向后移动，得到$A[i+b]$的数量增加$a-b$，$A[i+b+1]$的数量减少$a-b$。这样，我们就可以将$A[i]$减少到$b$的数量，而需要进行的操作次数为$a-b$。

综上所述，我们可以得到以下算法：

1. 统计两个数组$A$和$B$。
2. 初始化可信度之和为0。
3. 从后向前遍历数组$A$和$B$，对于每一个位置$i$：
   • 如果$A[i] < B[i]$，那么将可信度之和增加$B[i] - A[i]$。
   • 如果$A[i] > B[i]$，那么将可信度之和增加$(A[i] - B[i]) \times (B[i] + 1)$。
   • 如果$A[i] = B[i]$，那么将可信度之和增加$B[i]$。
4. 将可信度之和对$998244353$取模，并输出结果。

时间复杂度分析

统计两个数组$A$和$B$的时间复杂度为$O(n)$，遍历数组$A$和$B$的时间复杂度为$O(n)$，因此总的时间复杂度为$O(n)$。由于$n$的最大值为$2000$，所以算法的时间复杂度是可以接受的。

代码实现

MOD = 998244353

def divination(n, cards1, cards2):
    # 统计两个数组A和B
    A = [0] * (max(cards1) + 1)
    B = [0] * (max(cards2) + 1)
    for card in cards1:
        A[card] += 1
    for card in cards2:
        B[card] += 1
    
    # 计算可信度之和
    confidence = 0
    for i in range(len(A)-1, 0, -1):
        if A[i] < B[i]:
            confidence = (confidence + B[i] - A[i]) % MOD
        elif A[i] > B[i]:
            confidence = (confidence + (A[i] - B[i]) * (B[i] + 1)) % MOD
        else:
            confidence = (confidence + B[i]) % MOD
    
    return confidence

# 读取输入
n = int(input())
cards1 = list(map(int, input().split()))
cards2 = list(map(int, input().split()))

# 调用函数并输出结果
print(divination(n, cards1, cards2))
``