占卜 - 算法题解 - 常规

占卜 - 算法题解

题目背景

LHY 擅长使用卡牌进行占卜。

题目描述

LHY 在占卜的时候会提前准备两套数字卡牌，每套有 'n' 张。

每次占卜 LHY 会先从第一套卡牌中抽取若干张(至少一张)，称为'先验结果'；然后从第二套卡牌中抽取若干张(至少一张)，称为'后验结果'。

然后 LHY 会进行降神仪式，仪式中每次操作可以将先验结果或后验结果中的一张牌的数值 +1。如果可以通过最少 'x' 次操作使得先验结果与后验结果相同(即先验和后验这两个可重集合相同)，那么本次占卜的可信度为 'x'，否则为 0。

可以发现，LHY 的占卜产生的结果是有限的，也就是说，LHY 每次抽取先验结果和后验结果的情况总数为 (2^n-1) × (2^n-1) ，请你计算一下LHY占卜所有情况下的可信度之和。

输入格式

第一行一个正整数 'n' 表示每套卡牌的数量。

第二行 'n' 个正整数，表示第一套卡牌的数值。

第三行 'n' 个正整数，表示第二套卡牌的数值。

输出格式

一个整数，表示可信度之和。

由于答案可能很大，需要对 998244353 取模。

样例 #1

样例输入 #1

2
1 2
1 1

样例输出 #1

3
(说明：可信度不为0的情况有以下三种
先验{2} 后验{1} x=1
先验{2} 后验{1} x=1
先验{1 2} 后验{1 1} x=1)

提示

数据范围

对于 10% 的数据，'n' ≤ 10。
对于 50% 的数据，'n' ≤ 100。
对于 100% 的数据，1 ≤ 'n' ≤ 2000, 1 ≤ 卡牌数值 ≤ 10^5。

解题思路

首先，我们可以将先验结果和后验结果的卡牌数值统计出来，得到两个数组'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'。

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

统计两个数组'A'和'B'。
初始化可信度之和为0。
从后向前遍历数组'A'和'B'，对于每一个位置'i'：
- 如果'A[i] < B[i]'，那么将可信度之和增加'B[i] - A[i]'。
- 如果'A[i] > B[i]'，那么将可信度之和增加'(A[i] - B[i]) × (B[i] + 1)'。
- 如果'A[i] = B[i]'，那么将可信度之和增加'B[i]'。
将可信度之和对 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))