行と列の入れ替えで生成可能な一意な行列の数を求めるC++プログラム

問題の概要

サイズ n x n の行列が与えられます。各要素は一意であり、1 から n2 までの整数です。 以下の操作を任意の回数、任意の順序で実行できます。

• 列の入れ替え: 2つの列インデックス x, y (1 ≤ x < y ≤ n) を選び、それらの列を入れ替える。ただし、全ての行 i について mat[i][x] + mat[i][y] ≤ k を満たす必要があります。
• 行の入れ替え: 2つの行インデックス x, y (1 ≤ x < y ≤ n) を選び、それらの行を入れ替える。ただし、全ての列 j について mat[x][j] + mat[y][j] ≤ k を満たす必要があります。

これらの操作によって生成される 相異なる行列の総数 を、998244353 で割った余りで求めます。

例えば、n = 3, k = 15, mat = {{4, 3, 6}, {5, 9, 7}, {1, 2, 8}} の場合、答えは 36 になります。

解法のアプローチ

行の入れ替えと列の入れ替えは独立に考えられるため、それぞれについて「どのインデックス同士が入れ替え可能か」をグラフとして構築し、連結成分を求めます。

1. 入れ替え可能グラフの構築

• 行グラフ (pk): 行 i と行 j の間に辺を張る条件は、全列 l で mat[i][l] + mat[j][l] ≤ k が成り立つことです。これにより、この連結成分内の行は任意の順序で並べ替え可能になります。
• 列グラフ (e): 列 i と列 j の間に辺を張る条件は、全行 l で mat[l][i] + mat[l][j] ≤ k が成り立つことです。同様に、連結成分内の列は任意に並べ替え可能です。

2. 連結成分と順列の数

各グラフで DFS (深さ優先探索) を行い、連結成分のサイズを求めます。 サイズ s の連結成分内では、要素を s! (階乗) 通りに並べ替えられます。 行と列の操作は独立なので、全体の行列の数は以下の式で求まります。

答え = (Π (行の連結成分のサイズ!)) × (Π (列の連結成分のサイズ!)) mod 998244353

3. 事前計算

制約上、最大 50 程度までの階乗を法 998244353 で事前計算しておき、高速にアクセスできるようにします。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;

// DFSで連結成分のノードをスタックに収集
void dfs(int v, vector<int> graph[], vector<bool>& visited, vector<int>& component) {
    if (visited[v]) return;
    visited[v] = true;
    component.push_back(v);
    for (int nv : graph[v]) {
        dfs(nv, graph, visited, component);
    }
}

void solve(int n, int k, const vector<vector<int>>& mat) {
    // 階乗の事前計算 (n ≤ 50 想定)
    vector<long long> fact(51);
    fact[0] = 1;
    for (int i = 1; i <= 50; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }

    // 行グラフ (pk) と列グラフ (e) の構築
    vector<int> row_graph[n];
    vector<int> col_graph[n];

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            // 行 i と行 j が入れ替え可能か判定
            bool ok_row = true;
            for (int l = 0; l < n; ++l) {
                if (mat[i][l] + mat[j][l] > k) {
                    ok_row = false;
                    break;
                }
            }
            if (ok_row) {
                row_graph[i].push_back(j);
                row_graph[j].push_back(i);
            }

            // 列 i と列 j が入れ替え可能か判定
            bool ok_col = true;
            for (int l = 0; l < n; ++l) {
                if (mat[l][i] + mat[l][j] > k) {
                    ok_col = false;
                    break;
                }
            }
            if (ok_col) {
                col_graph[i].push_back(j);
                col_graph[j].push_back(i);
            }
        }
    }

    long long res_row = 1, res_col = 1;
    vector<bool> vis_row(n, false), vis_col(n, false);

    // 行の連結成分ごとに階乗を掛け合わせる
    for (int i = 0; i < n; ++i) {
        if (!vis_row[i]) {
            vector<int> comp;
            dfs(i, row_graph, vis_row, comp);
            if (!comp.empty()) {
                res_row = (res_row * fact[comp.size()]) % MOD;
            }
        }
    }

    // 列の連結成分ごとに階乗を掛け合わせる
    for (int i = 0; i < n; ++i) {
        if (!vis_col[i]) {
            vector<int> comp;
            dfs(i, col_graph, vis_col, comp);
            if (!comp.empty()) {
                res_col = (res_col * fact[comp.size()]) % MOD;
            }
        }
    }

    cout << (res_row * res_col) % MOD << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 3, k = 15;
    vector<vector<int>> mat = {
        {4, 3, 6},
        {5, 9, 7},
        {1, 2, 8}
    };
    solve(n, k, mat); // 出力: 36
    return 0;
}

実行例

入力:

n = 3, k = 15
mat = {{4, 3, 6}, 
       {5, 9, 7}, 
       {1, 2, 8}}

出力:

36

計算量の分析

• 時間計算量: O(n^3) (グラフ構築で全ペア O(n^2) × 判定 O(n)、DFS O(n^2))
• 空間計算量: O(n^2) (グラフの隣接リスト、行列の保存)

このアプローチにより、制約条件下で効率的に一意な行列の数を数え上げることができます。