P2220 [HAOI2012]容易题

题面:https://www.luogu.org/problem/P2220

如题,这真是一道简单题.
很容易想到如果没有限制条件ans=(1+2+...+n)*(1+2+...+n)*...*(1+2+...+n)
那么如果有限制条件的话直接在括号里减去相应的限制条件即可.

Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<map>
using namespace std;
const int mod=1e9+7,N=1e5+5;
long long n,m,k,ans,sum[N];
int cnt;
struct Node{
    long long x,y;
}a[N];
bool cmp(Node a1,Node a2){
    if(a1.x==a2.x){
        return a1.y<a2.y;
    }
    return a1.x<a2.x;
}
long long ksm(long long x,long long y){
    long long ret=1;
    while(y){
        if(y&1){
            ret=(ret*x)%mod;
        }
        x=(x*x)%mod;
        y>>=1;
    }
    return ret;
}
int main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    long long tot=(n*(n+1)/2)%mod;
    for(int i=1;i<=k;i++){
        scanf("%lld%lld",&a[i].x,&a[i].y);
    }
    sort(a+1,a+k+1,cmp);
    for(int i=1;i<=k;i++){
        if(a[i].x!=a[i-1].x){
            sum[++cnt]=tot;
        }
        else{
            if(a[i].y==a[i-1].y){
                continue;
            }
        }
        sum[cnt]=(sum[cnt]-a[i].y+mod)%mod;
    }
    ans+=ksm(tot,m-cnt);
    for(int i=1;i<=cnt;i++){
        ans=(ans*sum[i]+mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}