【每日一题】[HAOI2012]容易题(EASY) (组合数学)

Description

给出 个数字，每个数字范围是 的自然数，有 个限制
注意:

Solution

从数据范围得知要从 入手
若没有限制条件，则每一个位置都能放
答案为
可见每一个位置的地位都是相同的，限制条件只是改变某一个位置的值
但是实际上最多只能改变 个位置，剩下的 个位置直接用快速幂算就好了
于是记录这 个限制范围分别在哪一个数字上，由于位置的地位是相同的，不妨离散化一下
注意需要去重，直接用一个set存就好了
时间复杂度

Code

#include<bits/stdc++.h>

typedef long long ll;
using namespace std;
const int N = 1e6 + 5;
const int mod = 1000000007;

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
set<int> G[100005];
void solve() { 
    int n, m, k; cin >> n >> m >> k;
    map<int, int> mp;
    ll one = (1LL * n * (n + 1)) / 2 % mod;
    int cnt = 0;
    for (int i = 1; i <= k; i++) {
        int l, r; cin >> l >> r;
        if (!mp.count(l)) {
            mp[l] = ++cnt;
        } 
        G[mp[l]].insert(r);
    }
    int last = m - cnt;
    ll ans = qpow(one, last);
    for (int i = 1; i <= cnt; i++) {
        ll cur = one;
        for (auto &it : G[i]) {
            cur = ((cur - it) % mod + mod) % mod;
        }
        ans = ans * cur % mod;
    }
    cout << ans << '\n';
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0),  cout.tie(0);
  int T = 1; //cin >> T;
  while(T--) {
    solve();
  }
  return 0;
}