思路

简单的来说就是一个乘法分配律= =..
对于有限制的,去掉那些限制数,没限制的,都可选,然后将这m个数相乘即是答案.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=1e5+5;
struct ask{
    int l,r;
}a[N];

ll c[N];
bool cmp(ask A,ask B)
{
    if(A.l==B.l)    return A.r<B.r;
    else            return A.l<B.l;
}

ll qp(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1)    res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

int main()
{
    ll n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)    cin>>a[i].l>>a[i].r;
    sort(a+1,a+1+k,cmp);
    ll cnt=0;//记录有多少个数有限制- -
    ll sum=n*(n+1)/2%mod;
    for(int i=1;i<=k;i++)
    {
        if(a[i].l!=a[i-1].l)
        {
            c[++cnt]=sum;
        }
        else
        {
            if(a[i].r==a[i-1].r)    continue;
        }
        c[cnt]=((c[cnt]-a[i].r)%mod+mod)%mod;
    }
    ll ans=qp(sum,m-cnt);
    for(int i=1;i<=cnt;i++)
    {
        ans=(ans*c[i]%mod+mod)%mod;
    }
    cout<<ans<<'\n';
    return 0;
}