結果

問題 No.2503 Typical Path Counting Problem on a Grid
ユーザー Алексей ДанилюкАлексей Данилюк
提出日時 2023-10-13 22:07:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 235 ms / 2,000 ms
コード長 6,603 bytes
コンパイル時間 1,297 ms
コンパイル使用メモリ 124,984 KB
最終ジャッジ日時 2025-02-17 07:18:50
ジャッジサーバーID
(参考情報)
judge4 / judge6
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void solve()’:
main.cpp:290:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  290 |         scanf("%lld%lld", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
main.cpp: In function ‘int main()’:
main.cpp:328:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  328 |         scanf("%d", &t);
      |         ~~~~~^~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
#include <climits>
using namespace std;
#ifdef LOCAL
#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
#define eprintf(...) 42
#endif
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
#define mp make_pair
#define all(x) (x).begin(),(x).end()
clock_t startTime;
double getCurrentTime() {
return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}
ll floor_div(ll x, ll y) {
assert(y != 0);
if (y < 0) {
y = -y;
x = -x;
}
if (x >= 0) return x / y;
return (x + 1) / y - 1;
}
ll ceil_div(ll x, ll y) {
assert(y != 0);
if (y < 0) {
y = -y;
x = -x;
}
if (x <= 0) return x / y;
return (x - 1) / y + 1;
}
const uint MOD = 998244353;
template<uint mod = MOD> struct mint { // 1000000007 1000000009
uint x;
mint() : x(0) {}
mint(ll _x) {
_x %= mod;
if (_x < 0) _x += mod;
x = _x;
}
mint& operator += (const mint &a) {
x += a.x;
if (x >= mod) x -= mod;
return *this;
}
mint& operator -= (const mint &a) {
x += mod - a.x;
if (x >= mod) x -= mod;
return *this;
}
mint& operator *= (const mint &a) {
x = (ull)x * a.x % mod;
return *this;
}
mint pow(ll pw) const {
mint res = 1;
mint cur = *this;
while(pw) {
if (pw & 1) res *= cur;
cur *= cur;
pw >>= 1;
}
return res;
}
mint inv() const {
assert(x != 0);
uint t = x;
uint res = 1;
while(t != 1) {
uint z = mod / t;
res = (ull)res * (mod - z) % mod;
t = mod - t * z;
}
return res;
}
mint& operator /= (const mint &a) {
return *this *= a.inv();
}
mint operator + (const mint &a) const {
return mint(*this) += a;
}
mint operator - (const mint &a) const {
return mint(*this) -= a;
}
mint operator * (const mint &a) const {
return mint(*this) *= a;
}
mint operator / (const mint &a) const {
return mint(*this) /= a;
}
bool sqrt(mint &res) const {
if (mod == 2 || x == 0) {
res = *this;
return true;
}
if (pow((mod - 1) / 2) != 1) return false;
if (mod % 4 == 3) {
res = pow((mod + 1) / 4);
return true;
}
int pw = (mod - 1) / 2;
int K = 30;
while((1 << K) > pw) K--;
while(true) {
mint t = myRand(mod);
mint a = 0, b = 0, c = 1;
for (int k = K; k >= 0; k--) {
a = b * b;
b = b * c * 2;
c = c * c + a * *this;
if (((pw >> k) & 1) == 0) continue;
a = b;
b = b * t + c;
c = c * t + a * *this;
}
if (b == 0) continue;
c -= 1;
c *= mint() - b.inv();
if (c * c == *this) {
res = c;
return true;
}
}
assert(false);
}
bool operator == (const mint &a) const {
return x == a.x;
}
bool operator != (const mint &a) const {
return x != a.x;
}
bool operator < (const mint &a) const {
return x < a.x;
}
};
template<uint mod = MOD> struct Factorials {
using Mint = mint<mod>;
vector<Mint> f, fi;
Factorials() : f(), fi() {}
Factorials(int n) {
n += 10;
f = vector<Mint>(n);
fi = vector<Mint>(n);
f[0] = 1;
for (int i = 1; i < n; i++)
f[i] = f[i - 1] * i;
fi[n - 1] = f[n - 1].inv();
for (int i = n - 1; i > 0; i--)
fi[i - 1] = fi[i] * i;
}
Mint C(int n, int k) {
if (k < 0 || k > n) return 0;
return f[n] * fi[k] * fi[n - k];
}
};
template<uint mod = MOD> struct Powers {
using Mint = mint<mod>;
vector<Mint> p, pi;
Powers() : p(), pi() {}
Powers(int n, Mint x) {
n += 10;
if (x == 0) {
p = vector<Mint>(n);
p[0] = 1;
} else {
p = vector<Mint>(n);
pi = vector<Mint>(n);
p[0] = pi[0] = 1;
Mint xi = x.inv();
for (int i = 1; i < n; i++) {
p[i] = p[i - 1] * x;
pi[i] = pi[i - 1] * xi;
}
}
}
Mint pow(int n) {
if (n >= 0)
return p[n];
else
return pi[-n];
}
};
template<uint mod = MOD> struct Inverses {
using Mint = mint<mod>;
vector<Mint> ii;
Inverses() : ii() {}
Inverses(int n) {
n += 10;
ii = vector<Mint>(n);
ii[1] = 1;
for (int x = 2; x < n; x++)
ii[x] = Mint() - ii[mod % x] * (mod / x);
}
Mint inv(Mint x) {
assert(x != 0);
uint t = x.x;
uint res = 1;
while(t >= (int)ii.size()) {
uint z = mod / t;
res = (ull)res * (mod - z) % mod;
t = mod - t * z;
}
return ii[t] * res;
}
};
using Mint = mint<>;
struct Matrix {
Mint a[2][2];
Matrix() {
a[0][0] = a[1][1] = 1;
a[0][1] = a[1][0] = 0;
}
Matrix operator * (const Matrix &A) const {
Matrix R = Matrix();
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++) {
R.a[i][j] = 0;
for (int h = 0; h < 2; h++)
R.a[i][j] += a[i][h] * A.a[h][j];
}
return R;
}
};
Matrix bin_pow(Matrix A, ll p) {
if (p == 0) return Matrix();
if (p & 1) return A * bin_pow(A, p - 1);
return bin_pow(A * A, p / 2);
}
const int N = (int)1e7 + 77;
Mint dp[N];
void solve() {
ll n, m;
scanf("%lld%lld", &n, &m);
if (n > m) swap(n, m);
m -= n;
n++;
/*
if (m == 0) {
Mint ans = dp[n] * dp[n] + dp[n - 1] * dp[n - 1] * (n - 1);
printf("%u\n", ans.x);
return;
}
*/
Matrix A = Matrix();
A.a[0][0] = A.a[1][1] = 0;
A.a[0][0] = 2 * n - 1;
A.a[0][1] = 1;
A.a[1][0] = n - 1;
A.a[1][1] = 0;
A = bin_pow(A, m);
Mint ans = 0;
ans += dp[n] * (A.a[0][0] * dp[n] + A.a[0][1] * dp[n - 1] * (n - 1));
ans += dp[n - 1] * (A.a[1][0] * dp[n] + A.a[1][1] * dp[n - 1] * (n - 1));
printf("%u\n", ans.x);
return;
}
int main() {
startTime = clock();
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
dp[1] = 1;
for (int i = 1; i + 3 < N; i++) {
dp[i + 1] += dp[i] * 2 * i;
dp[i + 2] += dp[i] * i;
}
int t;
scanf("%d", &t);
for (int i = 1; i <= t; i++) {
eprintf("--- Case #%d start ---\n", i);
//printf("Case #%d: ", i);
solve();
//printf("%lld\n", (ll)solve());
/*
if (solve()) {
printf("Yes\n");
} else {
printf("No\n");
}
*/
eprintf("--- Case #%d end ---\n", i);
eprintf("time = %.5lf\n", getCurrentTime());
eprintf("++++++++++++++++++++\n");
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0