[题目链接]
https://www.lydsy.com/JudgeOnline/problem.php?id=2751
[算法]
考虑k = 0的情况 , 根据乘法原理 :
Ans = (n * (n + 1) / 2) ^ m
那么 , 对于k > 0 , 只需将用一棵平衡树维护每个位置应减小的值即可
详见代码
时间复杂度 : O(NlogN)
[代码]
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int P = 1e9 + 7; int n , m , k; map<int , int> mp; map< pair<int , int> , bool> existed; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); } template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); } template <typename T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } inline int exp_mod(int a , int n) { int b = a , res = 1; while (n > 0) { if (n & 1) res = 1ll * res * b % P; b = 1ll * b * b % P; n >>= 1; } return res; } int main() { read(n); read(m); read(k); for (int i = 1; i <= k; ++i) { int x , y; read(x); read(y); if (existed[make_pair(x , y)]) continue; existed[make_pair(x , y)] = true; mp[x] += y; } int cnt = (1ll * n * (n + 1) >> 1) % P , rest = m - (int)mp.size(); int ans = exp_mod(cnt , rest); for (map<int , int> :: iterator it = mp.begin(); it != mp.end(); it++) ans = (1ll * ans * ((cnt - it -> second % P) % P + P) % P) % P; printf("%d\n" , ans); return 0; }