题解 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; } ```