P15129 [ROIR 2026] 筹码放置

发现当一个矩阵完全包含另一个时，那个被包含的矩阵的限制是无效的。
考虑将有效的矩阵拉出来，按照宽度排序，从前到后处理。
设 \(f_i\) 表示前 \(i\) 个矩阵，\(i\) 矩阵内是有点的，\(i+1\) 及以后都没有点的方案数。
转移的时候考虑枚举一个 \(j\) 表示上一个放在了 \(j\) 矩阵内，并且 \(j\) 到 \(i\) 目前都没有放点。
得到转移

\[\begin{array}{lr} f_i=\sum_{j=0}^{i-1}f_j\times(c_i-c_j)\times(r_i-r_{i+1})\\ =(r_i-r_{i+1})\times\sum_{j=0}^{i-1}f_j\times(c_i-c_j)\\ =(r_i-r_{i+1})\times(c_i\times\sum_{j=0}^{i-1}f_j-\sum_{j=0}^{i-1}c_j\times f_j)) \end{array} \]

维护个前缀和即可做到 \(\mathcal{O}(n)\) 转移，加上排序 \(\mathcal{O}(n\log(n))\)

代码

/*
Luogu P15129 [ROIR 2026] 筹码放置
2026-03-09
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{
    template<typename T>
    inline void read(T&x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=x*10+c-'0',c=getchar();
        f?x=-x:0;
    }
    template<typename T>
    inline void write(T x){
        if(x==0){putchar('0');return ;}
        x<0?x=-x,putchar('-'):0;short st[50],top=0;
        while(x) st[++top]=x%10,x/=10;
        while(top) putchar(st[top--]+'0');
    }
    inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}
    inline void write(char c){putchar(c);}
    inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}
    inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}
    template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}
    template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}
    template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
template<int mod>struct Modint{
    int z;
    Modint(){z=0;}
    Modint(int x){x%=mod;z=x<0?x+mod:x;}
    Modint(long long x){x%=mod;z=x<0?x+mod:x;}
    Modint(short x){x%=mod;z=x<0?x+mod:x;}
    Modint(char x){x%=mod;z=x<0?x+mod:x;}
    Modint(bool x){x%=mod;z=x<0?x+mod:x;}
    friend Modint operator+(Modint t,Modint t2){Modint ans;ans.z=(t.z+t2.z)%mod;return ans;}
    friend Modint operator*(Modint t,Modint t2){Modint ans;ans.z=1ll*t.z*t2.z%mod;return ans;}
    friend Modint operator-(Modint t,Modint t2){Modint ans;ans.z=(t.z-t2.z)%mod;return ans;}
    Modint operator<<(const int t)const{Modint ans;ans.z=(z<<t)%mod;return ans;}
    Modint operator>>(const int t)const{Modint ans;ans.z=(z>>t)%mod;return ans;}
    Modint&operator+=(const Modint t){z=(z+t.z)%mod;return *this;}
    Modint&operator*=(const Modint t){z=1ll*z*t.z%mod;return *this;}
    Modint&operator-=(const Modint t){z=(z-t.z)%mod;return *this;}
    Modint&operator<<=(const int t){z=(z<<t)%mod;return *this;}
    Modint&operator>>=(const int t){z=(z>>t)%mod;return *this;}
    friend Modint ksm(Modint a,int b){
        Modint ans=1;
        while(b){if(b&1) ans=ans*a;a=a*a,b>>=1;}
        return ans;
    }
    friend void read(Modint&z){
        int x=0;char c=getchar();bool f=0;
        while(!isdigit(c)) c=='-'?f=1:0,c=getchar();
        while(isdigit(c)) x=(x*10ll+c-'0')%mod,c=getchar();
        f?x=-x:0;
        z.z=x;
    }
    friend void write(Modint x){x.z<0?x.z+=mod:0;write(x.z);}
};
const int mod=1000000007,maxn=200010;
#define M Modint<mod>
int n,m;
struct node{
    int r,c;
    bool operator<(const node t)const{
        if(r==t.r) return c>t.c;
        return r>t.r;
    }
}a[maxn],p[maxn];
M f[maxn];
signed main(){
    read(n,m);
    for(int i=1;i<=n;i++) read(p[i].r,p[i].c);
    sort(p+1,p+1+n);
    int cnt=0,maxx=0;
    for(int i=1;i<=n;i++){
        if(p[i].c<=maxx) continue;
        a[++cnt]=p[i],maxx=p[i].c;
    }
    n=cnt;f[0]=1;a[n+1].c=m,a[0].r=m;
    M h1=1,h2=1*a[0].c;
    for(int i=1;i<=n;i++){
        f[i]+=h1*a[i].c;f[i]-=h2;
        f[i]*=(a[i].r-a[i+1].r);
        h1+=f[i],h2+=f[i]*a[i].c;
    }
    M mi=1;
    for(int i=1;i<=n+1;i++) mi*=ksm(M(2),(1ll*(a[i].c-a[i-1].c)*(m-a[i].r))%(mod-1));
    M ans=0;
    for(int i=0;i<=n;i++) ans+=f[i];
    write(ans*mi);
    return 0;
}