qoj3082 Ascending Matrix 题解

题目链接

点击打开链接

题目解法

不考虑第 \(a_{r,c}=v\) 的限制怎么求？
我们把条件形式化一下，发现 \(k\) 个区域的颜色可以表示成轮廓线的形式，即第 \(i-1\) 条到第 \(i\) 条轮廓线之间的格点颜色为 \(i\)
问题变成找到 \(k-1\) 条互不穿过的路径，起点为 \((1,m)\)，终点为 \((n,1)\) 的方案数（下文中令 \(k:=k-1\)）
考虑把互不穿过转化成不能经过相同点，怎么转化？
若 \((i,j)\) 的左上方有 \(x\) 条轮廓线（包括这个点），则把 \((i,j)\) 的坐标变成 \((i+x,j+x)\)
现在的起点就变成了 \((2,m+1),...,(1+k,m+k)\)，终点变成了 \((n+1,2),...,(n+k,1+k)\)
画图不难理解这个转化的图像意义
这个问题就很典了，用 \(LGV\) 引理可以求出方案数

考虑加入 \(a_{r,c}=v\) 的限制
根据上面的转化，问题等价于 \((r+v-1,c+v-1)\) 的上方恰好有 \(v-1\) 条轮廓线
用生成函数表示，即令起点 \((1+x,m+x)\) 到终点 \((n+y,1+y)\) 的轮廓线在 \((r+v-1,c+v-1)\) 下方的方案数为 \(f_{x,y,0}\)，上方的为 \(f_{x,y,1}\)
那么答案就是 \(e_{i,j}=f_{i,j,0}+f_{i,j,1}x\) 的行列式的 \(x^{v-1}\) 前面的系数

直接求多项式复杂度就爆了
考虑用点值求多项式
取 \(k+1\) 个点值求行列式，然后做一遍拉格朗日插值即可
时间复杂度 \(O(k^4+nk^2)\)

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int K=110,N=410,P=998244353;
int n,m,k,r,c,v;
int fac[N],ifac[N],inv[N];
int f[K][K][2],e[K][K],knap[K],g[K];
inline void inc(int &x,int y){ x+=y;if(x>=P) x-=P;}
inline void dec(int &x,int y){ x-=y;if(x<0) x+=P;}
int det(){
    int w=1;
    F(i,1,k) F(j,i+1,k){
        while(e[i][i]){
            int div=e[j][i]/e[i][i];
            F(q,i,k) dec(e[j][q],1ll*e[i][q]*div%P);
            swap(e[i],e[j]),w*=-1;
        }
        swap(e[i],e[j]),w*=-1;
    }
    int res=w;F(i,1,k) res=1ll*res*e[i][i]%P;
    return (res+P)%P;
}
int bin(int x,int y){ if(x<y||y<0) return 0;return 1ll*fac[x]*ifac[y]%P*ifac[x-y]%P;}
int calc(int x1,int y1,int x2,int y2){ return bin(x2-x1+y1-y2,x2-x1);}
int qmi(int x,int y){
    int res=1;for(;y;y>>=1){ if(y&1) res=1ll*res*x%P;x=1ll*x*x%P;}
    return res;
}
void comb(int n){
    fac[0]=1;F(i,1,n) fac[i]=1ll*fac[i-1]*i%P;
    ifac[n]=qmi(fac[n],P-2);DF(i,n-1,0) ifac[i]=1ll*ifac[i+1]*(i+1)%P;
    F(i,1,n) inv[i]=1ll*ifac[i]*fac[i-1]%P;
}
int main(){
    comb(N-1);
    read(n),read(m),read(k),read(r),read(c),read(v);k--;
    r+=v-1,c+=v-1;
    F(i,1,k) F(j,1,k){
        f[i][j][0]=calc(i,m+i,n+j,j);
        F(det,0,min(r,c)){
            int val=1ll*calc(i,m+i,r-det,c-det)*calc(r-det,c-det,n+j,j)%P;
            dec(f[i][j][0],val);
            if(det) inc(f[i][j][1],val);
        }
    }
    F(x,1,k+1){
        F(i,1,k) F(j,1,k) e[i][j]=(f[i][j][0]+1ll*f[i][j][1]*x)%P;
        g[x]=det();
    }
    int ans=0;
    F(i,1,k+1){
        ms(knap,0);knap[0]=1;
        F(j,1,k+1) if(i!=j){
            int iv;
            if(i-j>=0) iv=inv[i-j];else iv=P-inv[j-i];
            DF(q,k,0){
                knap[q]=(P-1ll*knap[q]*j%P*iv%P+P)%P;
                if(q) inc(knap[q],1ll*knap[q-1]*iv%P);
            }
        }
        inc(ans,1ll*knap[v-1]*g[i]%P);
    }
    printf("%d\n",ans);
    return 0;
}