题解：P15129 [ROIR 2026] 筹码放置

· · 题解

首先单调栈去掉包含在另一个矩形内的矩形都会吧。

先设 sum1 为其他的没被矩形包含的方格数量（可选可不选，有两种选择），最后要乘上去。

然后就暂时没有思路了，不过注意到我们可以按纵坐标从大到小计算，如下图：

令 dp_i 为目前填完前 i 行矩形的方案数（有些行可以不填）。

首先这一行如果不填可以直接从上一个状态转移过来，即 dp_{i-1}\to dp_i。

考虑这一行的每一个格子，由于题目限制如果填了某一列的块中的格子，就意味着在之前包含这个块的矩形的所有其他格子都没有被填过。

例如现在填了 (3,2) 中的一个方格，那么这之前就不能填 (2,2) 内的格子，也不能填 (2,1) 内的格子，但可以填 (1,1) 内的格子。

那么填第 i 行的第 j 个格子就等价于从 dp_{j-1} 转移（因为其他的格子都不能填），再算上填 (i,j) 的方案数，即：\sum c_i\times r_j\times dp_{j-1}\to dp_i。

到这里我们已经有了 O(n^2) 的算法了。我们又注意到 c_i 在单行计算中是固定的，r_j\times dp_{j-1} 在所有计算中都是固定的，所以我们将 c_i 提出来，再对 r_j\times dp_{j-1} 做前缀和，然后就做完了。

最终答案就是 dp_n\times 2^{sum1}。

计数题还是太美妙了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10,P=1e9+7;
struct node{int x,y;}a[N];
bool cmp(node n1,node n2){return n1.x<n2.x;}
int dp[N],r[N],c[N];
int qpow(int a,int b){int ans=1;for(;b;b>>=1,a=a*a%P)if(b&1)ans=ans*a%P;return ans;}
signed main()
{
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    vector<node>stk;
    for(int i=1;i<=n;i++)
    {
        while(!stk.empty()&&stk.back().y<=a[i].y)stk.pop_back();
        stk.push_back(a[i]);
    }
    int lst=0,msum=0;
    for(auto y:stk)
    {
        msum+=(m-y.y)*(y.x-lst);
        lst=y.x;
    }
    msum+=m*(m-lst);
    dp[0]=1;int sum=0,len=stk.size();lst=0;
    for(int i=1;i<len;i++)c[i]=stk[i-1].y-stk[i].y;c[len]=stk[len-1].y;
    r[1]=stk[0].x;for(int i=2;i<=len;i++)r[i]=stk[i-1].x-stk[i-2].x;
    for(int i=1;i<=len;i++)
    {
        sum=(sum+dp[i-1]*r[i])%P;
        dp[i]=(sum*c[i]+dp[i-1])%P;
    }
    cout<<dp[len]*qpow(2,msum)%P;
    return 0;
}