結果
| 問題 |
No.3096 Snake Path
|
| コンテスト | |
| ユーザー |
 ecottea
|
| 提出日時 | 2025-08-17 03:06:54 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 23 ms / 2,000 ms |
| コード長 | 9,550 bytes |
| コンパイル時間 | 4,010 ms |
| コンパイル使用メモリ | 264,344 KB |
| 実行使用メモリ | 8,576 KB |
| 最終ジャッジ日時 | 2025-08-17 03:07:00 |
| 合計ジャッジ時間 | 5,601 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 35 |
ソースコード
#ifndef HIDDEN_IN_VS // 折りたたみ用
// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS
// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;
// 型名の短縮
using ll = long long; using ull = unsigned long long; // -2^63 ～ 2^63 = 9e18（int は -2^31 ～ 2^31 = 2e9）
using pii = pair<int, int>; using pll = pair<ll, ll>; using pil = pair<int, ll>; using pli = pair<ll, int>;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>;
using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vvvvl = vector<vvvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;
// 定数の定義
const double PI = acos(-1);
const vi DX = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
const vi DY = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;
// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;
// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), x))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), x))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索（昇順）
#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了
#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定
// 汎用関数の定義
template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; } // 非負整数乗
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）
template <class T> inline int getb(T set, int i) { return (set >> i) & T(1); } // 第iビット
template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod
// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }
#endif // 折りたたみ用
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#ifdef _MSC_VER
#include "localACL.hpp"
#endif
using mint = modint998244353;
//using mint = static_modint<1000000007>;
//using mint = modint; // mint::set_mod(m);
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;
#endif
#ifdef _MSC_VER // 手元環境（Visual Studio）
#include "local.hpp"
#else // 提出用（gcc）
int mute_dump = 0;
int frac_print = 0;
#if __has_include(<atcoder/all>)
namespace atcoder {
inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
}
#endif
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : -1; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : -1; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define dump(...)
#define dumpel(...)
#define dump_math(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す
#endif
//【単純パスの列挙（始点，終点指定）】O(?)
/*
* グラフ g の ST から GL への単純パス全てを格納した二次元リストを返す．
*/
template <class G>
vvi enumerate_simple_path(const G& g, int ST, int GL) {
// verify : https://mojacoder.app/users/RedSpica/contests/RedSpica-Regular-Selection/tasks/7
int n = sz(g);
vvi paths;
vi seq; // 訪れた頂点の列
// 頂点を訪れたことを記録しておくテーブル
vb seen(n);
// 再帰用の関数
function<void(int)> dfs = [&](int s) {
// s を訪れたことを記録
seen[s] = true;
seq.push_back(s);
// GL にたどり着いたら単純パスを記録
if (s == GL) {
paths.push_back(seq);
}
// まだ GL にたどり着いていないなら先を探索
else {
repe(t, g[s]) {
// 探索済なら何もしない．
if (seen[t]) continue;
// 未探索の頂点を探索しにいく．
dfs(t);
}
}
// s を訪れた記録を削除
seen[s] = false;
seq.pop_back();
};
dfs(ST);
return paths;
}
vm naive(int n) {
int h = 3, w = n;
Graph g(h * w);
rep(i, h) rep(j, w - 1) {
g[i * w + j].push_back(i * w + (j + 1));
g[i * w + (j + 1)].push_back(i * w + j);
}
rep(i, h - 1) rep(j, w) {
g[i * w + j].push_back((i + 1) * w + j);
g[(i + 1) * w + j].push_back(i * w + j);
}
int st = 0 * w + 0;
int gl = w & 1 ? (h - 1) * w + (w - 1) : 0 * w + (w - 1);
auto paths = enumerate_simple_path(g, st, gl);
vm cnt(h * w);
repe(path, paths) {
int L = sz(path);
int e = 0;
rep(l, L - 1) {
int i = path[l] / w;
int j = path[l] % w;
int i2 = path[l + 1] / w;
int j2 = path[l + 1] % w;
if (j > j2) {
swap(i, i2);
swap(j, j2);
}
if (j < j2) {
if (j & 1) {
if (i != 0) e++;
}
else {
if (i != h - 1) e++;
}
}
}
//dump(path, ":", e);
cnt[e]++;
}
return cnt;
}
void zikken() {
vvm tbl;
repi(n, 1, 15) {
dump(n);
tbl.push_back(naive(n));
}
dumpel(tbl);
dump_math(tbl);
exit(0);
}
/*
{ { 1, 0, 0 }, {1,2,0,0,0,0}, {1,4,4,2,1,0,0,0,0}, {1,6,12,12,6,1,0,0,0,0,0,0}, {1,8,24,38,35,14,2,2,1,0,0,0,0,0,0}, {1,10,40,88,120,95,36,14,9,2,0,0,0,0,0,0,0,0}, {1,12,60,170,309,364,258,110,54,24,4,2,1,0,0,0,0,0,0,0,0}, {1,14,84,292,666,1037,1080,726,344,170,69,23,12,3,0,0,0,0,0,0,0,0,0,0}, {1,16,112,462,1271,2458,3362,3194,2095,1054,531,234,96,38,7,2,1,0,0,0,0,0,0,0,0,0,0}, {1,18,144,688,2220,5131,8668,10670,9467,6122,3230,1691,780,320,118,35,15,4,0,0,0,0,0,0,0,0,0,0,0,0}, {1,20,180,978,3625,9752,19586,29574,33420,28132,18094,9978,5357,2496,1054,426,156,56,11,2,1,0,0,0,0,0,0,0,0,0,0,0,0}, {1,22,220,1340,5614,17241,40112,71670,98514,103762,83907,54103,30904,16775,7952,3554,1511,557,188,51,18,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {1,24,264,1782,8331,28774,76098,156914,253933,322362,320373,251538,163274,95598,52309,25480,11857,5082,1922,710,238,78,16,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {1,26,312,2312,11936,45815,135764,317198,590269,877426,1040852,986283,758184,495878,295430,163185,81592,38837,16878,6772,2660,910,284,72,21,6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {1,28,364,2938,16605,70148,230274,601118,1263858,2152432,2972552,3327762,3033135,2296824,1512852,913042,509403,260236,126065,56154,23597,9404,3288,1116,347,104,22,2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} };
これを 2D Rational チェッカーにぶち込んで漸化式を自動生成する．
(1 - 2 w z - w^2 z^4 + w^3 z^5 + w^4 z^6)/(1 - w - 2 w z - 2 w^3 z^3 -
w^2 z^4 + w^3 z^5 + 2 w^4 z^5 + w^4 z^6 + w^5 z^6)
なお 2D P-recursive チェッカーでは LLL 併用してもだめだった．
*/
int main() {
// input_from_file("input.txt");
// output_to_file("output.txt");
// zikken();
int n, K;
cin >> n >> K;
vvm dp(n + 10, vm(K + 10));
dp[0][0] = 1;
dp[1][1] = -2;
dp[2][4] = -1;
dp[3][5] = 1;
dp[4][6] = 1;
repi(i, 0, n) repi(j, 0, K) {
dp[i + 1][j + 0] += dp[i][j] * 1;
dp[i + 1][j + 1] += dp[i][j] * 2;
dp[i + 3][j + 3] += dp[i][j] * 2;
dp[i + 2][j + 4] += dp[i][j] * 1;
dp[i + 3][j + 5] += dp[i][j] * (-1);
dp[i + 4][j + 5] += dp[i][j] * (-2);
dp[i + 4][j + 6] += dp[i][j] * (-1);
dp[i + 5][j + 6] += dp[i][j] * (-1);
}
mint res = 0;
repi(j, 0, K) res += dp[n][j];
EXIT(res);
}