占卜 - 卡牌占卜可信度之和计算

占卜 - 卡牌占卜可信度之和计算

题目背景

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。

代码示例

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

const int MOD = 998244353;

int main() {
    int n;
    cin >> n;
    vector<int> prior(n), post(n);
    for (int i = 0; i < n; ++i) {
        cin >> prior[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> post[i];
    }

    unordered_map<int, int> cnt;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ++cnt[prior[i] - post[j]];
        }
    }

    long long ans = 0;
    for (auto& [diff, freq] : cnt) {
        ans = (ans + freq * freq) % MOD;
    }

    cout << ans << endl;

    return 0;
}

说明

首先，我们需要统计先验结果和后验结果之间的差值，然后根据差值的频次计算可信度之和。

具体来说，我们可以使用一个哈希表 'cnt' 来记录每个差值出现的次数。我们遍历先验结果和后验结果的所有组合，计算差值，并将其加入到哈希表中。然后，我们遍历哈希表，将每个差值的频次的平方加到答案中。

最后，我们输出答案并取模。