結果
問題 | No.2503 Typical Path Counting Problem on a Grid |
ユーザー |
![]() |
提出日時 | 2023-10-13 23:02:16 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 845 ms / 2,000 ms |
コード長 | 3,234 bytes |
コンパイル時間 | 3,537 ms |
コンパイル使用メモリ | 276,936 KB |
実行使用メモリ | 315,776 KB |
最終ジャッジ日時 | 2024-09-15 18:52:00 |
合計ジャッジ時間 | 12,745 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
#include<bits/stdc++.h>namespace {#pragma GCC diagnostic ignored "-Wunused-function"#include<atcoder/all>#pragma GCC diagnostic warning "-Wunused-function"using namespace std;using namespace atcoder;#define rep(i,n) for(int i = 0; i < (int)(n); i++)#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)#define all(x) begin(x), end(x)#define rall(x) rbegin(x), rend(x)template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }using ll = long long;using P = pair<int,int>;using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;using mint = modint998244353;template<class T, T (*add)(T, T), T (*zero)(), T (*mul)(T, T), T (*one)(), int N>struct Mat : array<array<T, N>, N> {using M = Mat<T, add, zero, mul, one, N>;void make_identity() {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {(*this)[i][j] = zero();}}for (int i = 0; i < N; i++) {(*this)[i][i] = one();}}M& operator+=(const M& rhs) {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {(*this)[i][j] = add((*this)[i][j], rhs[i][j]);}}return *this;}M& operator*=(const M& rhs) {static M temp;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {temp[i][j] = zero();}}for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {for (int k = 0; k < N; k++) {temp[i][k] = add(temp[i][k], mul((*this)[i][j], rhs[j][k]));}}}*this = temp;return *this;}M operator*(const M& rhs) {M res = *this;res *= rhs;return res;}template <class I>void inplace_pow(I k) {assert(k >= 0);static M temp;temp = *this;make_identity();while (k) {if (k & 1) *this *= temp;k >>= 1;if (k) temp *= temp;}}friend ostream& operator<<(ostream& os, const M& A) {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {os << A[i][j] << " \n"[j + 1 == N];}}return os;}};// mintmint add(mint x, mint y) { return x + y; }mint zero() { return mint(); }mint mul(mint x, mint y) { return x * y; }mint one() { return mint::raw(1); }using M = Mat<mint, add, zero, mul, one, 2>;} int main() {ios::sync_with_stdio(false);cin.tie(0);constexpr int SZ = 10000010;vector<M> memo1(SZ), memo2(SZ);rep(i, SZ) {memo1[i][0] = {2 * (i + 1), i + 1};memo1[i][1] = {1, 0};memo2[i][0] = {2 * i, i - 1};memo2[i][1] = {1, 0};}rep(i, SZ - 1) {M t = memo1[i];t *= memo1[i + 1];memo1[i + 1] = t;}for (int i = 2; i < SZ; i++) {memo2[i] *= memo2[i - 1];}int tt;cin >> tt;while(tt--) {ll n, m;cin >> n >> m;if (n > m) swap(n, m);if (n == 0) {cout << 1 << '\n';continue;}M b;b[0] = {2 * n + 1, n};b[1] = {1, 0};b.inplace_pow(m - n);M a = memo1[n - 1] * b * memo2[n];mint ans = a[0][0];cout << ans.val() << '\n';}}