結果

問題 No.2503 Typical Path Counting Problem on a Grid
ユーザー tofu_dra2tofu_dra2
提出日時 2023-10-13 22:58:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 450 ms / 2,000 ms
コード長 6,276 bytes
コンパイル時間 5,287 ms
コンパイル使用メモリ 268,944 KB
実行使用メモリ 42,496 KB
最終ジャッジ日時 2024-09-15 18:47:06
合計ジャッジ時間 8,261 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 125 ms
42,496 KB
testcase_01 AC 189 ms
42,368 KB
testcase_02 AC 168 ms
42,496 KB
testcase_03 AC 277 ms
42,480 KB
testcase_04 AC 389 ms
42,328 KB
testcase_05 AC 245 ms
42,368 KB
testcase_06 AC 441 ms
42,340 KB
testcase_07 AC 450 ms
42,388 KB
testcase_08 AC 310 ms
42,424 KB
testcase_09 AC 394 ms
42,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>

typedef long long int ll;
typedef long double ld;

using namespace std;
using namespace atcoder;

template <class T>
struct Matrix {
  vector<vector<T> > A;

  Matrix() = default;
  Matrix(int n, int m) : A(n, vector<T>(m, T())) {}
  Matrix(int n) : A(n, vector<T>(n, T())){};

  int H() const { return A.size(); }

  int W() const { return A[0].size(); }

  int size() const { return A.size(); }

  inline const vector<T> &operator[](int k) const { return A[k]; }

  inline vector<T> &operator[](int k) { return A[k]; }

  static Matrix I(int n) {
    Matrix mat(n);
    for (int i = 0; i < n; i++) mat[i][i] = 1;
    return (mat);
  }

  Matrix &operator+=(const Matrix &B) {
    int n = H(), m = W();
    assert(n == B.H() && m == B.W());
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++) (*this)[i][j] += B[i][j];
    return (*this);
  }

  Matrix &operator-=(const Matrix &B) {
    int n = H(), m = W();
    assert(n == B.H() && m == B.W());
    for (int i = 0; i < n; i++)
      for (int j = 0; j < m; j++) (*this)[i][j] -= B[i][j];
    return (*this);
  }

  Matrix &operator*=(const Matrix &B) {
    int n = H(), m = B.W(), p = W();
    assert(p == B.H());
    vector<vector<T> > C(n, vector<T>(m, T{}));
    for (int i = 0; i < n; i++)
      for (int k = 0; k < p; k++)
        for (int j = 0; j < m; j++) C[i][j] += (*this)[i][k] * B[k][j];
    A.swap(C);
    return (*this);
  }

  Matrix &operator^=(long long k) {
    Matrix B = Matrix::I(H());
    while (k > 0) {
      if (k & 1) B *= *this;
      *this *= *this;
      k >>= 1LL;
    }
    A.swap(B.A);
    return (*this);
  }

  Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); }

  Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); }

  Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); }

  Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); }

  bool operator==(const Matrix &B) const {
    assert(H() == B.H() && W() == B.W());
    for (int i = 0; i < H(); i++)
      for (int j = 0; j < W(); j++)
        if (A[i][j] != B[i][j]) return false;
    return true;
  }

  bool operator!=(const Matrix &B) const {
    assert(H() == B.H() && W() == B.W());
    for (int i = 0; i < H(); i++)
      for (int j = 0; j < W(); j++)
        if (A[i][j] != B[i][j]) return true;
    return false;
  }

  friend ostream &operator<<(ostream &os, const Matrix &p) {
    int n = p.H(), m = p.W();
    for (int i = 0; i < n; i++) {
      os << (i ? "" : "") << "[";
      for (int j = 0; j < m; j++) {
        os << p[i][j] << (j + 1 == m ? "]\n" : ",");
      }
    }
    return (os);
  }

  T determinant() const {
    Matrix B(*this);
    assert(H() == W());
    T R = 1;
    for (int i = 0; i < H(); i++) {
      int idx = -1;
      for (int j = i; j < W(); j++) {
        if (B[j][i] != 0) {
          idx = j;
          break;
        }
      }
      if (idx == -1) return 0;
      if (i != idx) {
        R *= T(-1);
        swap(B[i], B[idx]);
      }
      R *= B[i][i];
      T inv = T(1) / B[i][i];
      for (int j = 0; j < W(); j++) {
        B[i][j] *= inv;
      }
      for (int j = i + 1; j < H(); j++) {
        T a = B[j][i];
        if (a == 0) continue;
        for (int k = i; k < W(); k++) {
          B[j][k] -= B[i][k] * a;
        }
      }
    }
    return R;
  }
};

#define inf 1010000000
#define llinf 1001000000000000000ll
#define pi 3.141592653589793238
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define rep1(i, n) for(ll i = 1; i <= (n); i++)
#define rep2(i,l,r) for(ll i = (l); i < (r); i++)
#define per(i, n) for(ll i = (n)-1; i >= 0; i--)
#define each(x, v) for (auto&& x : v)
#define rng(a) a.begin(),a.end()
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define st string
#define pcnt __builtin_popcountll
#define bit(n) (1LL<<(n))

template <class T = ll>
inline T in(){ T x; cin >> x; return (x);}
#define vcin(x,n) {for(ll loop=0; loop<(n); loop++) cin>>x[loop];}

#define dame { puts("-1"); return 0;}
#define yes { puts("Yes"); return 0;}
#define no { puts("No"); return 0;}
#define ret(x) { cout<<(x)<<endl;}
#define rets(x) { cout<<(x)<< " ";}
#define Endl cout<<endl;
#define dump(x) { cout << #x << " = " << (x) << endl;}

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false;}

// 仮マクロ 便利だったら昇格
#define unique(v) v.erase( unique(v.begin(), v.end()), v.end())
// ここまで仮マクロ

// clock()/CLOCKS_PER_SEC 秒数を知りたいときに用いる

#define mod 998244353
using mint = modint998244353;

/*

#define mod 1000000007
using mint = modint1000000007;

*/

vector<ll> dx={1,0,-1,0};
vector<ll> dy={0,1,0,-1};

using pl = pair<ll,ll>;
using ppl = pair<pl,ll>;
// G.assign(n, vector<ll>()); グローバル変数にGを置く時に置く

// 関数を置くのはここ以下

// 行列ライブラリ
// できること：
// Matrix<mint> M(n)    -> n*n行列の生成
// Matrix<mint> M(n,m)  -> n*m行列の生成
// M[a][b] = x の形で代入できる
// M.H() M.W() で縦横の長さを出力
// += -= *= ^= で普通の行列計算ができる(累乗は高速,掛算は愚直)
// == != も使える
// << で出力可能(mintの時は関数の書き換えが必要)
// M.determinant() で行列式計算(mint以外だとバグる)

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  ll T = in();
  // 前計算
  vector<mint> v(10010000);
  v[1] = 1;
  v[2] = 2;
  rep(i,10010000){
    if(i<=2) continue;
    v[i] = v[i-1] * 2 * (i-1) + v[i-2] * (i-2);
  }

  rep(_,T){
    ll n,m; cin >> n >> m; n++;m++;
    if(n>m) swap(n,m);
    if(n==1){
      ret(1)
      continue;
    }
    Matrix<mint> M(2);
    M[0][0] = 2*n-1;
    M[0][1] = n-1;
    M[1][0] = 1;
    M[1][1] = 0;
    M ^= m-n;
    Matrix<mint> M2(2,1);
    M2[0][0] = v[n];
    M2[1][0] = v[n-1];
    M *= M2;
    mint ans;
    ans += M[0][0] * 2 * (n-1);
    ans += M[1][0] * (n-1);
    ans *= v[n-1];
    ans += M[0][0] * (n-2) * v[n-2];
    ret(ans.val());
  }
}
0