给一个n*n的矩阵，保证：(1)每行都是一个排列 (2)每行每个位置和上一行对应位置不同。求这个矩阵在所有合法矩阵中字典序排第几。
考虑类似数位DP的做法，枚举第几行开始不卡限制，那么显然之前的行都和题给矩阵相同，之后都是错排。现在要求的就是，当前行在所有与上一行不交的排列中字典序排第几。同样考虑数位DP，从后往前枚举到当前位开始不卡限制。用两个树状数组分别维护：(1)这一位之后的数组成的集合 (2)这一位之后当前行和上一行均有的数的集合。那么分当前这位是否使用上一行这一位之后存在的数讨论，现在要求的就是：在后n-i个位置中，有j个数可能会与上一行重合（也就是(2)中的数），的方案数。也就是：i位排列有j位要求错位的方案数dp[i][j]。我们有：dp[i][j]=dp[i][j-1]-dp[i-1][j-1]。（或者列出容斥DP式子，发现是一个卷积形式，于是NTT即可）1 #include2 #include 3 #include 4 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 5 typedef long long ll; 6 using namespace std; 7 8 const int N=2010,mod=998244353; 9 int n,ans,b[N],a[N][N],fac[N],dp[N][N],p[N];10 11 struct BIT{12 int c[N],sum;13 void clear(){ sum=0; memset(c,0,sizeof c); }14 void add(int x){ sum++; for (; x<=n; x+=x&-x) c[x]++; }15 int que(int x){ int res=0; for (; x; x-=x&-x) res+=c[x]; return res; }16 }t,T;17 18 void init(){19 fac[0]=1; rep(i,1,n) fac[i]=1ll*fac[i-1]*i%mod;20 dp[1][0]=1;21 rep(i,2,n){22 dp[i][0]=fac[i];23 rep(j,1,i) dp[i][j]=(dp[i][j-1]-dp[i-1][j-1]+mod)%mod;24 }25 p[0]=1; rep(i,1,n) p[i]=1ll*p[i-1]*dp[n][n]%mod;26 }27 28 void add(int x){ if (++b[x]==2) T.add(x); }29 void inc(int &x,int y){ x+=y; (x>=mod)?x-=mod:0; }30 31 int main(){32 freopen("1085g.in","r",stdin);33 freopen("1085g.out","w",stdout);34 scanf("%d",&n);35 rep(i,1,n) rep(j,1,n) scanf("%d",&a[i][j]);36 init(); int sm=0;37 rep(i,1,n) sm=(sm+1ll*fac[n-i]*(a[1][i]-1-t.que(a[1][i]-1)))%mod,t.add(a[1][i]);38 ans=1ll*sm*p[n-1]%mod;39 rep(i,2,n){40 t.clear(); T.clear(); sm=0; memset(b,0,sizeof(b));41 for (int j=n; j; j--){42 add(a[i][j]); add(a[i-1][j]); t.add(a[i][j]);43 int x=T.que(a[i][j]-1),y=t.que(a[i][j]-1)-x,z=T.sum;44 if (b[a[i-1][j]]==2 && a[i-1][j]