結果
問題 | No.2529 Treasure Hunter |
ユーザー |
![]() |
提出日時 | 2023-11-03 22:26:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 3,232 bytes |
コンパイル時間 | 1,145 ms |
コンパイル使用メモリ | 113,848 KB |
最終ジャッジ日時 | 2025-02-17 18:32:00 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 22 |
ソースコード
// #pragma GCC target("avx2")// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")#include <algorithm>#include <bitset>#include <cassert>#include <climits>#include <cmath>#include <complex>#include <deque>#include <iomanip>#include <iostream>#include <map>#include <queue>#include <set>#include <string>#include <tuple>#include <vector>using namespace std;using ll = long long;using pii = pair<int, int>;using pll = pair<ll, ll>;#define TEST cerr << "TEST" << endl#define AMARI 998244353// #define AMARI 1000000007#define TIME_LIMIT 1980000#define el '\n'#define El '\n'// n*nの正方行列。 ococo_gyouretu<型の名前> og(n);で宣言// 足し算・掛け算・べき乗(O(logN)のやつ)しかない。template <typename T> class ococo_gyouretu {public:int n;// ここに扱うデータが入ってるvector<vector<T>> a;ococo_gyouretu(int N) {n = N;a.resize(n);for(int i = 0; i < n; i++) a[i].resize(n);}ococo_gyouretu operator+(ococo_gyouretu const &r) const {ococo_gyouretu<T> ans(n);for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {ans[i][j] += a[i][j] + r.a[i][j];if(ans[i][j] >= AMARI) ans[i][j] -= AMARI;}}return ans;}ococo_gyouretu operator*(ococo_gyouretu const &r) const {ococo_gyouretu<T> ans(n);for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {for(int k = 0; k < n; k++) {ans.a[i][j] += a[i][k] * r.a[k][j];ans.a[i][j] %= AMARI;}}}return ans;}ococo_gyouretu bekizyou(ll b) {ococo_gyouretu<T> temp(n), ans(n);for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {temp.a[i][j] = a[i][j];ans.a[i][j] = (i == j ? 1 : 0);}}while(b) {if(b % 2) {ans = ans * temp;}temp = temp * temp;b /= 2;}return ans;}};#define MULTI_TEST_CASE truevoid solve(void) {ll w,h;cin >> w >> h;ococo_gyouretu<ll> g(3);//g[i][j] = ある行にi個あった時、次の行にj個置くのが何通りか//gは遷移行列g.a[0][0] = g.a[1][0] = g.a[2][0] = 1;g.a[0][1] = w; g.a[0][2] = max((w * (w - 1)) / 2 - w,0LL);g.a[1][1] = w - 1; g.a[1][2] = max(((w - 1) * (w - 2)) / 2 - (w - 2),0LL);g.a[2][1] = w - 2; g.a[2][2] = max(((w - 2) * (w - 3)) / 2 - (w - 4),0LL);for(int i = 0; i < 3; i++){for(int j = 0; j < 3; j++){g.a[i][j] %= AMARI;}}ococo_gyouretu<ll> ans = g.bekizyou(h);ll ansv = 0;for(int i = 0; i < 3; i++){ansv += ans.a[0][i];if(ansv < 0)ansv += AMARI;ansv %= AMARI;}cout << ansv << el;return;}void calc(void) {return;}signed main(void) {cin.tie(nullptr);ios::sync_with_stdio(false);calc();int t = 1;if(MULTI_TEST_CASE) cin >> t;while(t--) {solve();}return 0;}