pypy3 解法, 执行用时: 420ms, 内存消耗: 59728K, 提交时间: 2022-04-22 15:56:30

import sys
from collections import defaultdict

def read_ints():
    return map(int, sys.stdin.readline().split())

def binPow(a, n, m):
    res = 1
    while n:
        if n & 1:
            res = res * a % m
        a = a * a % m
        n >>= 1
    return res

MOD = 10 ** 9 + 7
n, m, k = read_ints()

dl = defaultdict(set)

for i in range(k):
    x, y = read_ints()
    dl[x].add(y)
# print(dl)
cnt = defaultdict(int)
N = (n+1) * n // 2

ans = 1
for x, l in dl.items():
    cnt[N - sum(l)] += 1

for c, k in cnt.items():
    ans = ans * binPow(c, k, MOD) % MOD

print(ans * binPow(N, m-len(dl), MOD) % MOD)

Python3 解法, 执行用时: 316ms, 内存消耗: 30660K, 提交时间: 2022-04-22 15:57:51

import sys
from collections import defaultdict

def read_ints():
    return map(int, sys.stdin.readline().split())

def binPow(a, n, m):
    res = 1
    while n:
        if n & 1:
            res = res * a % m
        a = a * a % m
        n >>= 1
    return res

MOD = 10 ** 9 + 7
n, m, k = read_ints()

dl = defaultdict(set)

for i in range(k):
    x, y = read_ints()
    dl[x].add(y)
# print(dl)
cnt = defaultdict(int)
N = (n+1) * n // 2

ans = 1
for x, l in dl.items():
    ans = ans * (N - sum(l)) % MOD

print(ans * binPow(N, m-len(dl), MOD) % MOD)

C++(clang++ 11.0.1) 解法, 执行用时: 171ms, 内存消耗: 11908K, 提交时间: 2022-10-17 10:32:33

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=1e9+7;
map<int,set<int>>mp;
ll qsm(ll a,ll b)
{
	a%=mod;
	ll res=1;
	while(b)
	{
		if(b&1)
		res=res*a%mod;
		a=a*a%mod;
		b/=2;
	}
	return res;
}
int  main()
{
	ll n,m,k,sum,ans;
	cin>>n>>m>>k;
	sum=n*(n+1)/2;
	for(int i=0;i<k;i++)
	{
		ll a,b;
		cin>>a>>b;
		mp[a].insert(b);
	}
	ans=qsm(sum,m-mp.size());
	for(auto x:mp)
	{
		ll t=sum;
		for(auto y:x.second)
		t-=y;
		ans=t%mod*ans%mod;
	}
	cout<<ans;
}