题解 CF1085G 【Beautiful Matrix】

· · 题解

设A表示给出的矩形,B表示一个字典序小于A的美丽矩形.

那么,我们应该计算对于所有行i,A与B的前i-1行相同,且A_i的字典序大于B_i的方案数.

显然,第一行直接康托展开一下即可

对于第2\rightarrow n行,每行的总方案数即为n的元素的错排数,这样每种方案的贡献也可以轻易计算.

然而麻烦的是,对于第i行,现在已经钦点B_{i-1}=A_{i-1},比较难计算存在多少种合法的B_i<A_i.

显然的是,对于第i行的每一列j,我们也计算A_i与B_i的前j-1列相同,且A_{i,j}>B_{i,j}的方案数即可

现在我们要考虑的问题是,已经钦点了A_i与B_i的前j-1列相同,且A_{i,j}>B_{i,j}的方案数后,如何快速计算后n-j列的合法方案数.

考虑这样一件事情,设S=\{A_{i-1,k}|k\in [1,j]\},T=\{B_{i,k}|k\in [1,j]\},y=|T|-|S\bigcap T|=|S|-|S\bigcap T|,那么(j,n]中将有y个位置不受限制,因为\forall k\in(j,n] 且A_{i-1,k}\in T-S\bigcap T,\nexists B_{i,k}=A_{i-1,k}.

考虑设f_{i,j}表示有i个元素的排列,需要满足j个限制的方案数.现在考虑\mathtt{DP}这个东西.

显然,f_{i,i}就是i个元素的错排数,f_{i,0}=i!

容易得出,f_{i,j}=f_{i,j-1}-f_{i-1,j-1}.

这样,每个位置都可以分两类讨论.

  1. 在B_{i,j}填一个<A_{i,j},且没有在A_{i-1,k}(k\in[1,j])中出现过的合法的数
  2. 在B_{i,j}填一个<A_{i,j},且已经在A_{i-1,k}(k\in[1,j])中出现过的合法的数

以上两种数的数量都可以通过树状数组轻易计算.

设S=\{A_{i-1,k}|k\in [1,j]\},T=\{A_{i,k}|k\in [1,j)\},x=|S|-|S\bigcap T|

若填了第一种数,那么方案数为f_{n-j,n-j-x}.

若填了第二种数,那么方案数为f_{n-j,n-j-x+1}.

int n;
int a[2005][2005];
long long f[2005][2005],g[2005];
long long fac[2005];
template<int T>
struct BIT
{
    int c[T];
    BIT(){memset(c,0,sizeof(c));}
    #define lowbit (x&-x)
    inline void add(int x,int val){for(;x<T;x+=lowbit)c[x]+=val;}
    inline int ask(int x){int re=0;for(;x;x-=lowbit)re+=c[x];return re;}
};
int main()
{
    read(n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            read(a[i][j]);
    fac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%p;
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        f[i][0]=fac[i];
        for(int j=1;j<=i;j++)
            f[i][j]=(f[i][j-1]-f[i-1][j-1]+p)%p;
    }
    for(int i=0;i<=n;i++)g[i]=f[i][i];
    long long ans=0;
    static bool vis[2005];
    for(int j=1;j<=n;j++)
    {
        int t=0;
        for(int i=1;i<a[1][j];i++)if(!vis[i])t++;
        ans=(ans+fac[n-j]*t)%p;
        vis[a[1][j]]=1;
    }
    ans=ans*power(g[n],n-1)%p;
    for(int i=2;i<=n;i++)
    {
        static BIT<2005> S,T;S=BIT<2005>();T=BIT<2005>(); 
        long long sum=0;
        static bool vis[2005];memset(vis,0,sizeof(vis));
        static bool used[2005];memset(used,0,sizeof(used));
        for(int j=1;j<=n;j++)
        {
            long long A=a[i][j]-1-S.ask(a[i][j]-1);
            long long B=T.ask(a[i][j]-1);
            if(vis[a[i-1][j]]==0&&a[i-1][j]<a[i][j])A--;//B_{i,j}=A_{i-1,j}的不合法方案数 
            if(vis[a[i-1][j]]==0)T.add(a[i-1][j],1);
            vis[a[i][j]]=1;
            int x=T.ask(n);
            sum=(sum+B*f[n-j][n-j-x+1]+(A-B)*f[n-j][n-j-x])%p;
            S.add(a[i][j],1);
            if(used[a[i][j]])T.add(a[i][j],-1);used[a[i-1][j]]=1;
        }
        ans=(ans+sum*power(g[n],n-i))%p;
    }
    printf("%lld\n",ans);
    return 0;
}