题解 | #分元宵#

1. 问题分析

本题本质上是一个带重复性的排列问题（Permutation with Repetition），或称之为从集合到集合的映射计数问题。

元宵种类数：每个元宵由“馅”和“皮”唯一确定。设馅的种类为 $\varsigma$ ，皮的种类为 $\vartheta$ ，则元宵的总种类 $T = \varsigma \times \vartheta$ 。
槽位总数：碗是放置元宵的物理位置。题目明确指出桌子和碗都有编号且不可改变位置，即每个槽位都是唯一且可区分的。设桌子数为 $\varpi$ ，每张桌子上的碗数为 $\varrho$ ，则总槽位数 $N = \varpi \times \varrho$ 。
重复性规则：
1. 每一只碗都必须装一个元宵。
2. 每一只碗装哪种元宵是独立的，不限制某种元宵的使用次数。

虽然题目描述中提及了桌子和碗的多层结构，但在全局视角下，所有碗构成了一个长度为 $N$ 的线性序列，每个位置有 $T$ 种选择。

2. 算法

2.1 数学公式

根据组合数学模型，共有 $N$ 个独立位置，每个位置有 $T$ 种独立选择，故总方案数 $W$ 为： $W = T^N \pmod \Lambda$ 代入已知变量： $W = (\varsigma \times \vartheta)^{\varpi \times \varrho} \pmod \Lambda$

2.2 运算优化

由于 $N$ 高达 $10^{12}$ ，直接进行连乘的时间复杂度为 $O(N)$ ，无法满足性能要求。必须采用快速幂算法（Binary Exponentiation / Exponentiation by Squaring）。

底数预处理：由于 $\varsigma$ 和 $\vartheta$ 极大，首先对底数进行取模运算： $T_{base} = ((\varsigma \pmod \Lambda) \times (\vartheta \pmod \Lambda)) \pmod \Lambda$ 注意：在进行 $\varsigma \pmod \Lambda$ 时需使用 64 位整型。
指数预处理：指数 $E = \varpi \times \varrho$ 。虽然 $E$ 可能达到 $10^{12}$ ，但在快速幂算法中，指数作为循环控制变量，直接存储在 64 位整型变量中即可，无需对模数取模（除非应用欧拉定理，但本题指数规模尚在标准整型范围内，直接计算更优）。
快速幂计算：通过将指数 $E$ 二进制分解，将复杂度降低至 $O(\log E)$ ，即 $O(\log(\varpi \cdot \varrho))$ 。

3. 代码实现

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

ll power(ll base, ll exp, ll mod) {
    if (mod == 1)
        return 0;
    ll sum = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) {
            sum = sum * base % mod;
        }
        base = base * base % mod;
        exp >>= 1;
    }
    return sum;
}

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

    ll a, b, c, d, mod;
    cin >> a >> b >> c >> d >> mod;

    ll T = (a % mod) * (b % mod) % mod;
    ll N = c * d;
    ll ans = power(T, N, mod);
    cout << ans << endl;
}

4. 复杂度分析

时间复杂度： $O(\log(\varpi \cdot \varrho))$ 。对于 $10^{12}$ 的规模，大约只需进行 40 次乘法取模运算，效率极高。
空间复杂度： $O(1)$ 。仅需常数级变量存储中间状态。