P11781 [COTS 2012] 机器统计 / MULTI

· · 题解

Link

平面上有若干一类点，每次询问在平面上加入一个一类点（询问间嘟立），求新增 k 个二类点，满足所有二类点横纵坐标不同且对每个二类点，存在一类点在其右上方（严格）的方案数。所有点坐标均为正整数，k\le 30。

为了方便将所有一类点坐标减一，将判定条件转为严格。

显然一类点的坐标为二类点框出了一个合法区域，这个区域是一个折线。如果没有新增点的操作，我们只需要在这个折线区域里放进 k 个横纵坐标不同的点。因为限制条件上紧下松，所以从上往下 dp 是容易的。

我们有单次 \mathcal{O(Vk)} 的 dp 做法。设 lim_i 为第 i 行的折线右边界，设 f_{i,j} 为从上到下第 i 行，已经填入了 j 个点的方案数。转移式是 f_{i,j}\leftarrow (lim_i-j+1)f_{i+1,j-1}+f_{i+1,j} 。答案即是 f_{1,k}。

考虑新加入的一类点，如果其在折线内部则不影响答案，如果在折线外部则会对折线上连续一段的右边界拓展。

关于拓展有一些性质：折线的前缀和后缀的转移是没有变化的，折线被修改的这一段的转移是完全相同的。那么我们就已经有一个用矩阵维护转移的 \mathcal{O(qk^3\log V)} 做法了，但这个跑不过去。考虑折线中间被修改的一段，如果我们知道在此之前选择了几个点，在这一段内又选择了几个点，那么贡献就是一个组合数。这过程是 \mathcal{O(k^2)} 的。既然能够快速计算被修改的段的贡献，那么我们只需要将前缀和后缀的答案合并上这个组合数即可。

设右边界被修改的区间长度是 len，区间内新的右边界是 L，在此之前选择了 i 个点，在段内选择了 j 个点，方案数就是 {len-i\choose j}{L\choose j}j!。

前缀的贡献就是上面的 f 数组，后缀的贡献应该怎么求？我们考虑 dp 的过程，因为 dp 是逐行的，我们只需要求出当前行每个元素贡献到答案位置 (1,k) 的系数即可。这个可以倒着 dp 求出，转移式与上面的 f 基本一致。至此，我们就解出这道题了，复杂度是 \mathcal{O(Vk+qk^2)}。

一个小问题是模数小于 V，如果使用预处理阶乘来求组合数，就会出现除 0 的搞笑局面。因为组合数下面的数很小，所以可以直接 \mathcal{O(Vk)} 求。

code

const int N=1e5+5,lm=1e5,mod=10009;

int f[N][33],g[N][33];
int C[N][33];
int J[N];

pir a[N];
int lim[N];
int rlim[N];

void add(int &x,int y){
    x=x+y>=mod?x+y-mod:x+y;
}

void init(int n,int k){
    C[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=min(i,k);j++)
            add(C[i][j],(j>0?C[i-1][j-1]:0)+C[i-1][j]);
    J[0]=1;
    for(int i=1;i<=n;i++)
        J[i]=1ll*J[i-1]*i%mod;
}

signed main(){
    int n=read(),k=read();
    for(int i=1;i<=n;i++)
        a[i]={read()-1,read()-1};
    init(lm,k);
    sort(a+1,a+1+n);reverse(a+1,a+1+n);
    f[lm+1][0]=1;
    for(int i=lm,j=1;i>=1;i--){
        lim[i]=lim[i+1];
        while(a[j].fi==i){
            lim[i]=max(lim[i],a[j].se);
            j++;
        }
        f[i][0]=1;
        for(int l=1;l<=k;l++)
            f[i][l]=(1ll*f[i+1][l-1]*max(0,lim[i]-l+1)+f[i+1][l])%mod;
    }
    lim[0]=1e9;
    reverse(lim,lim+1+lm);memcpy(rlim,lim,sizeof(lim));reverse(lim,lim+1+lm);//二分找到修改的区间长度，存一个倒序的右边界，在这上面二分
    g[1][k]=1;
    for(int i=2;i<=lm;i++){
        for(int j=0;j<=k;j++)
            g[i][j]=(g[i-1][j]+1ll*g[i-1][j+1]*max(0,lim[i-1]-j))%mod;
    }int q=read();
    while(q--){
        int x=read()-1,y=read()-1;
        if(lim[x]>=y)
            print(f[1][k]),pc('\n');
        else{
            int r=lm-(upper_bound(rlim+1,rlim+lm,y)-rlim-1);
            int len=x-r+1;
            int ans=0;
            for(int i=0;i<=k;i++){
                for(int j=0;j<=min(i,y);j++)
                    add(ans,1ll*f[x+1][j]*C[y-j][i-j]%mod*C[len][i-j]%mod*g[r][i]%mod*J[i-j]%mod);
            }print(ans),pc('\n');
        }
    }
    return 0;
}