[HAOI2012]

[HAOI2012]

题目链接：https://ac.nowcoder.com/acm/problem/19989

题目描述：

给你三个数n，m，k，n代表数的最大取值范围（1~n），m代表数列的长度，k代表限制的条数。
每条限制给出两个数x和y代表第x个数不能取y，（如果n为5，第三个数不能取2，3，则第三个数只能取1，4，5）。问所有取值范围内中的数列中的每个元素的积再把这些积的和输出出来。

思路：

先思考如果没有限制条件，答案会是什么？是所有数的取值加起来再相乘。也就是（1+2+3+...+n)(1+2+3+...+n)。。。,加了限制条件以后只需要把不能取的数剔除即可
因为k的取值范围是1e5，而数列的元素个数远大于k，所以最多只有k个数需要剔除，剩下的数用快速幂就能很快得出结果，把需要剔除的数的结果先计算出来加上快速幂得出的结果就是最终答案。

#include <bits/stdc++.h>
using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
#define ios ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define endl "\n"
#define int long long
const long long N = 1e6 + 7;
const long long mod = 1e9 + 7;
struct z {
    int x, y;
};
z num[N];
bool cmp(z a, z b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
int fastPow(int a, int n) {
    int ans = 1;
    while (n) {
        if (n & 1) ans = (a * ans) % mod;
        a = (a * a) % mod;
        n >>= 1;
    }
    return ans % mod;
}
signed main() {
    ios;
    int n, m, k;
    cin >> n >> m >> k;
    int I = (n + 1) % mod * n % mod / 2;
    I %= mod;
    for (int i = 1; i <= k; i++) cin >> num[i].x >> num[i].y;
    sort(num + 1, num + k + 1, cmp);
    int kind = 1, ans = 1, nans = I;
    nans -= num[1].y;
    for (int i = 2; i <= k; i++) {
        if (num[i].x != num[i - 1].x) {
            kind++;
            ans = (ans * nans) % mod;
            nans = I - num[i].y;
        } else {
            if (num[i].y != num[i - 1].y) nans -= num[i].y;
        }
    }
    ans = (ans * nans) % mod;
    ans = (ans * fastPow(I, m - kind) % mod + mod) % mod;
    cout << ans;
}