C++で解く：行の最小値と列の最大値を保持するシーケンス(A, B)のペア数を求めるアルゴリズム

この記事では、N×M のグリッドに対して特定の条件を満たすシーケンスのペア (A, B) の総数を求める問題を、C++ を使って効率的に解く方法を解説します。

問題の概要

3つの整数 N、M、K が与えられます。ここで、N 個の行（横方向）と M 個の列（縦方向）からなるグリッドを考えます。各セルには 1 以上 K 以下の整数を書き込むこととし、これをもとにシーケンス A と B を次のように定義します。

• 1 から N までの各 i について、A[i] は i 番目の行に含まれるすべての要素の最小値

• 1 から M までの各 j について、B[j] は j 番目の列に含まれるすべての要素の最大値

このとき、条件を満たすペア (A, B) の総数を求めます。答えが非常に大きくなる可能性があるため、結果は 998244353 で割った余りとして返します。

入力例と出力例

たとえば、N = 2、M = 2、K = 2 の場合、出力は 7 になります。これは、(A[1], A[2], B[1], B[2]) の組み合わせが以下の7通りになるためです。

• (1,1,1,1)、(1,1,1,2)、(1,1,2,1)、(1,1,2,2)
• (1,2,2,2)、(2,1,2,2)、(2,2,2,2)

解法のアプローチ

この問題は、各行の最小値がちょうど t になるような場合の数を、t = 1 から K まで順に足し合わせることで求められます。具体的な手順は以下の通りです。

p := 998244353
関数 power(a, b) を定義し、(a^b) mod p を返すようにする
メイン処理では以下を実行する:
n が 1 の場合:
    power(K, m) を返す
m が 1 の場合:
    power(K, n) を返す
ans := 0
t を 1 から K まで 1 ずつ増やしながら繰り返す:
    ans := (ans + (power(t, n) - power(t - 1, n) + p) mod p * power(K - t + 1, m)) mod p
ans を返す

考え方のポイント

power(t, n) - power(t-1, n) の部分は、「n 個の要素がすべて t 以下であり、かつ少なくとも1つがちょうど t である」ような構成の数、つまり行の最小値がちょうど t となる場合の数を表しています。一方、power(K - t + 1, m) は、その条件のもとで列の最大値として許容される B の構成数に対応します。これらを掛け合わせて t ごとに合計することで、全体のペア数が得られます。

C++による実装例

それでは、実際のコードを見てみましょう。

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

long p = 998244353;

long power(long a, long b, long ret = 1){
    for (; b; b >>= 1, a = a * a % p)
       if (b & 1)
          ret = ret * a % p;
    return ret;
}
long solve(int n, int m, int K){
    if (n == 1)
       return power(K, m);
    if (m == 1)
       return power(K, n);
    long ans = 0;
    for (long t = 1; t <= K; t++){
       ans = (ans + (power(t, n) - power(t - 1, n) + p) % p * power(K - t + 1, m)) % p;
    }
    return ans;
}
int main(){
   int N = 2;
   int M = 2;
   int K = 2;
   cout << solve(N, M, K) << endl;
}

実行結果

入力

2, 2, 2

出力

7

まとめ

本記事では、グリッドの行最小値・列最大値からなるシーケンスのペア数を数える問題を取り上げました。累乗計算を高速に行う power() 関数（繰り返し二乗法）を活用し、最小値ごとに場合を分けて合計するという方針により、計算量 O(K log N) で効率よく解答できます。競技プログラミングでも頻出の「mod 998244353」での剰余計算の扱い方も参考になるでしょう。