Problem F: 伊菲的飞船设计

📝 题目描述

🔑 算法模块

💡 思路分析

我们假定 \(n\le m\) ，想象 \(n\) 是这个长方形的高度。

\(n=1\) ，可以发现，两边的格子必须选，中间要选 \(2\) 个格子，也就是说 \(m\) 至少为 \(4\) 。现在，选中两端两个格子之后，只剩下了 \(m-2\) 个格子，先选上面，有 \(m-2\) 种情况，下面可以在剩下的 \(m-3\) 个格子中选一个 ，有 \(m-3\) 种情况，也就是说，答案为 \([m\geq 4](m-2)(m-3)\) 。

\(n \ge 2\) ，现在 \(m\ge 2\) ，方案一定存在，讨论：

选择 \(4\) 条边：\(n^2m^2\)

选择 \(4\) 条边，但恰好只有一个角落冲突：\(4nm-4\) （确定 \(1\) 个角落冲突，会占用两条相邻边，选择另外的两条边共有 \(n\times m\) 种方案，其中有 \(1\) 种方案会导致另外的两条边选择同一个格子，所以是 \(nm-1\)。这样的角落有 \(4\) 个，所以是 \(4nm-4\)）

选择 \(4\) 条边，但恰好有两个角落冲突：\(2\) （这两个角落必须相对，那么只有两种情况）

选择 \(4\) 条边，有三个及以上的角落冲突：0

答案就是：\(n^2m^2-(4nm-4+2)=n^2m^2-4nm+2\)

懒得求二次剩余，所以 \(+2\) 没取余也算你过啦（

🖥️ 代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    ll n, m, mod = 998244353;
    cin >> n >> m;
    if (n == 1 && m == 1) {
        cout << 0 << "\n";
    } else if (n == 1 || m == 1) {
        cout << (max(n, m) - 2) * (max(n, m) - 3) % mod << "\n";
    } else {
        cout << ((n * m - 4) % mod * n % mod * m % mod + 2) % mod << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int _ = 1;
    cin >> _;
    while (_--) {
        solve();
    }

    return 0;
}

⏱️ 复杂度分析

📚 拓展