题目
题目描述
为了使得大家高兴，小Q特意出个自认为的简单题（easy）来满足大家，这道简单题是描述如下：
有一个数列A已知对于所有的A[i]都是1~n的自然数，并且知道对于一些A[i]不能取哪些值，我们定义一个数列的积为该数列所有元素的乘积，要求你求出所有可能的数列的积的和 mod 1000000007的值，是不是很简单呢？呵呵！
输入描述
第一行三个整数n,m,k分别表示数列元素的取值范围，数列元素个数，以及已知的限制条数。
接下来k行，每行两个正整数x,y表示A[x]的值不能是y。
输出描述
一行一个整数表示所有可能的数列的积的和对1000000007取模后的结果。如果一个合法的数列都没有，答案输出0。
示例1
输入
3 4 5
1 1
1 1
2 2
2 3
4 3
输出
90
说明
样例解释
A[1]不能取1
A[2]不能去2、3
A[4]不能取3
所以可能的数列有以下12种
数列 积
2 1 1 1 2
2 1 1 2 4
2 1 2 1 4
2 1 2 2 8
2 1 3 1 6
2 1 3 2 12
3 1 1 1 3
3 1 1 2 6
3 1 2 1 6
3 1 2 2 12
3 1 3 1 9
3 1 3 2 18
备注
30%的数据 \(n \le 4,m \le 10,k \le 10\)
另有20%的数据 \({k=0}\)
70%的数据 \(n \le 1000,m \le 1000,k \le 1000\)
100%的数据 \(n \le 10^9,m \le 10^9,k \le 10^5,1 \le y \le n,1 \le x \le m\)
题解
知识点：组合数学。
因为是求乘积的总和，我们可以利用分配律，把式子等价变换成每个数字可能值的和（贡献）的乘积。
这是对含有分配律的式子的常见处理方式，比较典型的就是乘法对加法的分配律。当然，还有对纯加法，利用交换律的分组求和，比较典型的就是在处理子区间异或和之和问题中的拆位优化，对每位分组一并处理。
因此，如果都没有限制，那么总和应该为 \(\displaystyle \prod_{i=1}^m \sum_{j=1}^n j = \prod_{i=1}^m \frac{n(n+1)}{2} = \left( \frac{n(n+1)}{2} \right)^m\) 。
考虑加上约束，那么就是给某些数的贡献减去约束值的和 \(sum\) ，那么它们的贡献就为 \(\dfrac{n(n+1)}{2} - sum\) 。
时间复杂度 \(O(k \log k + \log m)\)
空间复杂度 \(O(k)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 1e9 + 7;
int qpow(int a, ll k) {
int ans = 1;
while (k) {
if (k & 1) ans = 1LL * ans * a % P;
k >>= 1;
a = 1LL * a * a % P;
}
return ans;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m, k;
cin >> n >> m >> k;
map<int, set<int>> mp;
for (int i = 1;i <= k;i++) {
int x, y;
cin >> x >> y;
mp[x].insert(y);
}
int ans = 1;
for (auto [x, st] : mp) {
int sum = 0;
for (auto y : st) (sum += y) %= P;
ans = 1LL * ans * (1LL * n * (n + 1) / 2 % P - sum + P) % P;
}
ans = 1LL * ans * qpow(1LL * n * (n + 1) / 2 % P, m - mp.size()) % P;
cout << ans << '\n';
return 0;
}