P2220 [HAOI2012] 容易题

思路

首先，我们考虑 $k = 0$ 的情况：

$$1 \times 1 + 1 \times 2 + \dots + 1 \times n + \dots + n \times 1 + n \times 2 + \dots + n \times n$$

然后用乘法分配律化简一下，得：

$$(\frac{n(n + 1)}{2})^m$$

然后我们可以直接推广到 $k \neq 0$ 的情况，得（其中 $a_i$ 表示第 $i$ 位受到限制之和）：

$$\prod_{i = 1}^{m}{(\frac{n(n + 1)}{2} - a_i)}$$

然后我们可以 $\Theta(n \log n)$ 求出 $a_i$。

因为 $n \leq 10^9$，所以我们不能直接暴力算，考虑将 $a_i$ 为 $0$ 和 $a_i$ 不为 $0$ 的情况分开处理。

因为 $a_i \neq 0$ 的数量最多为 $k$，然后剩下的部分可以快速幂算，时间复杂度 $\Theta(k \log n + \log n)$，明显能过。

Code

#include <bits/stdc++.h>  
#define int long long  
#define re register  
  
using namespace std;  
  
typedef pair<int,int> pii;  
const int mod = 1000000007,inv = 500000004;  
int n,m,k,num,sum = 1,t = 1;  
map<int,int> mp;  
map<pii,bool> vis;  
  
inline int read(){  
    int r = 0,w = 1;  
    char c = getchar();  
    while (c < '0' || c > '9'){  
        if (c == '-') w = -1;  
        c = getchar();  
    }  
    while (c >= '0' && c <= '9'){  
        r = (r << 3) + (r << 1) + (c ^ 48);  
        c = getchar();  
    }  
    return r * w;  
}  
  
inline int Add(int a,int b){  
    return (a + b) % mod;  
}  
  
inline int Sub(int a,int b){  
    return ((a - b) % mod + mod) % mod;  
}  
  
inline int Mul(int a,int b){  
    return a * b % mod;  
}  
  
inline int qmi(int a,int b){  
    int res = 1;  
    while (b){  
        if (b & 1) res = Mul(res,a);  
        a = Mul(a,a);  
        b >>= 1;  
    }  
    return res;  
}  
  
signed main(){  
    n = read();  
    m = read();  
    k = read();  
    sum = Mul(Mul(Add(1,n),n),inv);  
    for (re int i = 1;i <= k;i++){  
        int x,y;  
        x = read();  
        y = read();  
        if (!mp.count(x)) num++;  
        if (!vis.count({x,y})){  
            mp[x] = Add(mp[x],y);  
            vis[{x,y}] = true;  
        }  
    }  
    for (auto it = mp.begin();it != mp.end();it++) t = Mul(t,Sub(sum,it -> second));  
    printf("%lld",Mul(qmi(sum,m - num),t));  
    return 0;  
}