【NC19989】容易题(EASY)

题目

容易题(EASY)

乘法分配律
很多人都觉得这道题很简单以至于做了都侮辱智商，但是题解里面只有“显然”，“容易”，以及一堆 乱七八糟 简洁 的代码，没有说出规律是怎么得来的，令人费解。因此记录一下思路和推导。

思路

首先肯定是找规律，然而这道题涉及到可重复数的全排列，所以 n n n 和 m m m 稍微大一点点就会很难办（枚举的项数太多，指数级的），并且限制条件使问题更加复杂化了。所以枚举时先不考虑限制条件，即 k = 0 k=0 k=0，然后选择较小的数比如 n = 3 , m = 2 n=3,m=2 n=3,m=2，可以知道，一共会产生 n m = 9 n^m=9 nm=9 种可能，共有 9 9 9 个数列：

根据题意模拟计算，可以得出最终的答案为 36 36 36

但是我们没必要非得按题目给我们的描述来模拟，因为那看不出一点规律！

纵向观察表格，可以发现位置 1 1 1 按元素可以分为 3 3 3 组，每组的位置 2 2 2 处都是一个完整的 1 , 2 , 3 1,2,3 1,2,3 序列，这样，我们可以得出结果为：
1 × ( 1 + 2 + 3 ) + 2 × ( 1 + 2 + 3 ) + 3 × ( 1 + 2 + 3 ) = ( 1 + 2 + 3 ) × ( 1 + 2 + 3 ) = ( 1 + 2 + 3 ) 2 = 36 1\times(1+2+3)+2\times(1+2+3)+3\times(1+2+3)=(1+2+3)\times(1+2+3)=(1+2+3)^2=36 1×(1+2+3)+2×(1+2+3)+3×(1+2+3)=(1+2+3)×(1+2+3)=(1+2+3)2=36

这是一种巧算，利用了乘法分配律，根据上述规律，我们大胆猜想：

给定 n , m n,m n,m，并且没有限制条件，则总和为： ( 1 + 2 + 3 + . . . + n ) m (1+2+3+...+n)^m (1+2+3+...+n)m

验证：

我们将 m m m 增加 1 1 1，即 n = m = 3 n=m=3 n=m=3，那么上述表格可变为：

表格中省略的就是数列 1 − 9 1-9 1−9相同位置的数，它们是重复出现的！！

并且根据之前的计算，可以得出省略号处的总和为 36 = ( 1 + 2 + 3 ) 2 36=(1+2+3)^2 36=(1+2+3)2，那么现在的的总和怎么计算呢？很简单： 1 × ( 1 + 2 + 3 ) 2 + 2 × ( 1 + 2 + 3 ) 2 + 3 × ( 1 + 2 + 3 ) 2 = ( 1 + 2 + 3 ) 3 1\times(1+2+3)^2+2\times(1+2+3)^2+3\times(1+2+3)^2=(1+2+3)^3 1×(1+2+3)2+2×(1+2+3)2+3×(1+2+3)2=(1+2+3)3

以此类推，可以知道当 m m m 增加时，次方数就会增加，并且当 n n n 增加时，底数就会相应变成从 1 1 1 到 n n n 的和（这里不再赘述），所以上面的结论是成立的。

那么加了限制条件之后呢？

比如说，在 n = m = 3 n=m=3 n=m=3 的时候，我让位置 1 1 1 不能取 2 2 2，那么结果是不是就变成了 1 × ( 1 + 2 + 3 ) 2 + 3 × ( 1 + 2 + 3 ) 2 = ( 1 + 2 + 3 ) 2 × ( 1 + 2 + 3 − 2 ) 1\times(1+2+3)^2+3\times(1+2+3)^2=(1+2+3)^2\times (1+2+3-2) 1×(1+2+3)2+3×(1+2+3)2=(1+2+3)2×(1+2+3−2) 了呢？
那么让位置 1 1 1 不能取 2 ， 3 2，3 2，3 呢？那么结果就变成了 1 × ( 1 + 2 + 3 ) 2 = ( 1 + 2 + 3 ) 2 × ( 1 + 2 + 3 − 2 − 3 ) 1\times(1+2+3)^2=(1+2+3)^2\times(1+2+3-2-3) 1×(1+2+3)2=(1+2+3)2×(1+2+3−2−3)
那么让位置 1 1 1 不能取 2 ， 3 2，3 2，3，并且位置 2 2 2 不能取 1 1 1 呢？那么结果就变成了 1 × ( 1 + 2 + 3 ) × ( 1 + 2 + 3 − 1 ) = ( 1 + 2 + 3 ) 1 × ( 1 + 2 + 3 − 2 − 3 ) × ( 1 + 2 + 3 − 1 ) 1\times(1+2+3)\times(1+2+3-1)=(1+2+3)^1\times(1+2+3-2-3)\times(1+2+3-1) 1×(1+2+3)×(1+2+3−1)=(1+2+3)1×(1+2+3−2−3)×(1+2+3−1)
（注意必须按位置从小到大处理，相当于一层一层地剥离，才不会重复剥离而产生错误）

由此我们得出结论：

给出 n , m , k n,m,k n,m,k，如果没有限制条件，那么结果就是 ( 1 + 2 + . . . + n ) m (1+2+...+n)^m (1+2+...+n)m，如果有限制条件，那么结果就是 ( 1 + 2 + . . . + n ) m − k × ∏ i = 1 k ( ( 1 + 2 + . . . + n ) − s u m [ i ] ) (1+2+...+n)^{m-k}\times \prod_{i=1}^k((1+2+...+n)-sum[i]) (1+2+...+n)m−k×∏i=1k​((1+2+...+n)−sum[i])，其中 s u m [ i ] sum[i] sum[i] 表示位置 i i i 的限制数值得总和，比如位置 1 1 1 不能取 2 , 3 2,3 2,3，那么 s u m [ 1 ] = 2 + 3 = 5 sum[1]=2+3=5 sum[1]=2+3=5

代码

#include <iostream>
#include <map> // 注意是用 map 而不是 unordered_map，主要使用其有序性
#include <unordered_set>
using namespace std;
using LL = long long;

const int MOD = 1e9 + 7;

/**
 * @brief 快速幂
 *
 * @param a
 * @param b
 * @param p
 * @return int
 */
int quick_pow(int a, int b, int p) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res = ((LL)res * a) % p;
        }
        a = ((LL)a * a) % p;
        b >>= 1;
    }
    return res;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n = 0, m = 0, k = 0;
    cin >> n >> m >> k;
    // 存储下标 a 处被剔除的取值（哈希集合去重）
    map<int, unordered_set<int>> mp;
    // 存储下标 a 处被剔除的取值的总和
    map<int, LL> sums;
    int a = 0, b = 0;
    // 输入限制条件并处理
    for (int i = 0; i < k; i++) {
        cin >> a >> b;
        // 去重，如果已经存在则不管
        if (mp[a].count(b)) continue;
        // 加入集合
        mp[a].emplace(b);
        // 求总和
        sums[a] += b;
    }
    // 求从 1 开始的公差为 1 的等差数列的前 n 项和并对 MOD 取模
    int sum = ((LL)n * (n + 1) >> 1) % MOD;
    // 求无限制的项的结果
    a = quick_pow(sum, m - mp.size(), MOD);
    // 求有限制的项的结果
    // 由于 map 是天然从小到大有序的，所以直接遍历即可
    for (auto&& [_, v] : sums) {
        // 注意 sum - v 可能是负数，要将其限制为非负数
        a = (LL)a * (sum - v + MOD) % MOD;
    }
    // 输出结果
    cout << a << endl;
    return 0;
}