提出 #68200306

---

ソースコード 拡げる

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

// (a^p)%mod の long long 内計算（法<2^31.5に限る）
long long power_mod(long long a, long long p, long long mod) {
  if (p==0) return 1LL;
  if (p&1LL) {
    return (power_mod(a,p-1,mod)*a)%mod;
  } else {
    long long tmp = power_mod(a,p>>1,mod);
    return tmp*tmp%mod;
  }
}

// mod上での逆数計算（法<2^31.5に限る）
long long inverse(long long a, long long mod) {
  return power_mod(a,mod-2,mod);
}

/////////////////// メイン ///////////////////

int main () {
  
  /////////////////// 前入力 ///////////////////
  
  int q;
  cin >> q;

  int mod = 998244353;

  /////////////////// 前処理 ///////////////////

  // 階乗を計算してメモしておく
  vector<long long> factorial(400001,1LL);
  for (int i=2; i<=400000; i++) {
    factorial.at(i) = factorial.at(i-1) * i % mod; 
  }

  /////////////////// ループ ///////////////////

  // 問題数だけループ
  for (int loop=0; loop<q; loop++) {
    
    //////////////////// 入力 ////////////////////

    long long h, w, k;
    cin >> h >> w >> k;

    //////////////// 出力変数定義 ////////////////

    // k<h+w-2の場合は0が答えなので、0で初期化しておくことでif文の負担を減らす
    long long result = 0;

    //////////////////// 処理 ////////////////////

    // 最短経路しか取れない場合
    if (k==h+w-2) {

      // h+w-2回のうち、h-1回下へ、w-1回右へ
      result = factorial.at(h+w-2);
      result *= inverse(factorial.at(h-1)*factorial.at(w-1)%mod,mod);
      result %= mod;

    } else if (k==h+w-1) {

      // h+w-2回のうち、h-1回下へ、w-1回右へ
      result = factorial.at(h+w-2);
      result *= inverse(factorial.at(h-1)*factorial.at(w-1)%mod,mod);
      result %= mod;

      // 通らない1つを2*(w-1)*(h-1)個から選ぶ
      result *= (2*(w-1)*(h-1)) % mod;
      result %= mod;

    } else if (k==h+w) {

      // h+w-2回のうち、h-1回下へ、w-1回右へ
      result = factorial.at(h+w-2);
      result *= inverse(factorial.at(h-1)*factorial.at(w-1)%mod,mod);
      result %= mod;

      // 通らない2つを2*(w-1)*(h-1)個から選ぶ
      // *2*(w-1)*(h-1) と /2はあらかじめキャンセルしておく
      result *= (w-1)*(h-1) % mod;
      result %= mod;
      result *= (2*(w-1)*(h-1)-1) % mod;
      result %= mod;

      // 通らない2つでたまたま別経路ができちゃうパターンを求めて引く
      // h+w-3回のうち、h-2回下へ、w-2回右へ、1回「下右or右下」
      long long dup = factorial.at(h+w-3);
      dup *= inverse(factorial.at(h-2)*factorial.at(w-2)%mod,mod);
      dup %= mod;
      result -= dup;
      result %= mod;

      // 一度上に戻るパターンを求めて足す
      // h+w-2回のうち、h+1回下へ、w-3回右へ、を考えて、
      // 下のうち最初と最後以外どれかを「右上右」に変える
      if (w>2) {
        long long detour1 = factorial.at(h+w-2);
        detour1 *= inverse(factorial.at(h+1)*factorial.at(w-3)%mod,mod);
        detour1 %= mod;
        detour1 *= h-1;
        detour1 %= mod;
        result += detour1;
        result %= mod;
      }

      // 一度左に戻るパターンを求めて足す（上と同様）
      if (h>2) {
        long long detour2 = factorial.at(h+w-2);
        detour2 *= inverse(factorial.at(h-3)*factorial.at(w+1)%mod,mod);
        detour2 %= mod;
        detour2 *= w-1;
        detour2 %= mod;
        result += detour2;
        result %= mod;
      }

      // 引き算があったので、念のための負の数対策
      if (result<0) result += mod;

    }

    //////////////////// 出力 ////////////////////

    cout << result << endl;
    
  }

  /////////////////// 後処理 ///////////////////



  //////////////////// 終了 ////////////////////

  return 0;

}

提出情報

ジャッジ結果