AtCoder Regular Contest 107 C - Shuffle Permutation（并查集）

思路：
如果 x x x行能和 y y y行， z z z行交换，那么 y y y行也可以和 z z z行交换。
所以把能互相交换的部分（行，列）用并查集合并起来。每个能互相交换的连通块的总方案数就是连通块大小的阶乘。

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 105;
const int mod = 998244353;
int a[maxn][maxn];
int fa[maxn],siz[maxn];
ll fac[maxn];
int findset(int x) {
    if(fa[x] == x) return x;
    return fa[x] = findset(fa[x]);
}
void Union(int x,int y) {
    int rx = findset(x),ry = findset(y);
    if(rx != ry) {
        fa[rx] = ry;
        siz[ry] += siz[rx];
    }
}
int main() {
    int n,k;scanf("%d%d",&n,&k);
    fac[0] = 1;
    for(int i = 1;i <= n;i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    ll ans = 1;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= n;j++) {
            scanf("%d",&a[i][j]);
        }
    }
    for(int i = 1;i <= 2 * n;i++) {
        fa[i] = i;
        siz[i] = 1;
    }
    for(int i = 1;i <= n;i++) {
        for(int j = i + 1;j <= n;j++) {
            int flag1 = 1,flag2 = 1;
            for(int q = 1;q <= n;q++) {
                if(a[i][q] + a[j][q] > k) {
                    flag1 = 0;
                }
                if(a[q][i] + a[q][j] > k) {
                    flag2 = 0;
                }
            }
            if(flag1) {
                Union(i,j);
            }
            if(flag2) {
                Union(n + i,n + j);
            }
        }
    }
    for(int i = 1;i <= 2 * n;i++) {
        if(fa[i] == i) {
            ans = ans * fac[siz[i]] % mod;
        }
    }
    printf("%lld\n",ans);
    return 0;
}