結果

問題 No.3176 転移迷宮 (Hard)
ユーザー ymm-knight
提出日時 2025-06-10 20:30:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 761 ms / 3,000 ms
コード長 2,307 bytes
コンパイル時間 2,130 ms
コンパイル使用メモリ 200,096 KB
実行使用メモリ 76,736 KB
最終ジャッジ日時 2025-06-10 20:30:37
合計ジャッジ時間 21,831 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define Loop(x,l,r) for (ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for (ll x = ll(r)-1; x >= ll(l); --x)
#define Looc(x,l,r) for (ll x = ll(l); x <= ll(r); ++x)
#define LoocR(x,l,r) for (ll x = ll(r); x >= ll(l); --x)
#define int ll
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#ifndef DB
#define DB 0
#define endl '\n'
#endif
#define debugl(l) if constexpr ((l) < DB)
#define debug debugl(0)

template<class T>
struct LR {
	vector<T> vec;
	int offset;

	void init(int l, int r) {
		offset = l;
		vec.assign(r - l, {});
	}

	bool has(int i) {
		return offset <= i && i < offset + vec.size();
	}

	int from() { return offset; }
	int to() { return offset + vec.size(); }

	T &operator[](int i) {
		return vec[i - offset];
	}
};

const int mod = 998244353;

ll pw(ll x, ll y)
{
	x = (x%mod+mod)%mod;
	ll a = 1;
	while (y) {
		if (y%2)
			a = a*x % mod;
		x = x*x % mod;
		y /= 2;
	}
	return a;
}
ll inv(ll x) { return pw(x, mod-2); }

void solve()
{
	int n, k;
	cin >> n >> k;
	vector<pair<LR<ll>,ll>> vec(n);

	ll inv2k1 = inv(2*k+1);
	Loop (i,0,n) {
		int l = max<int>(0, i - k);
		int r = min<int>(n, i + k + 1);

		auto &v = vec[i].first;
		v.init(l, r);
		v[i] = 1;
		Loop (x,l,r)
			v[x] = (v[x] + mod - inv2k1) % mod;

		vec[i].second = 1;
	}

	auto add = [&](int dst, int src, ll ml) {
		auto &vd = vec[dst].first;
		auto &vs = vec[src].first;

		Loop (i, vs.from(), vs.to()) {
			if (!vs[i])
				continue;
			assert(vd.has(i));
			vd[i] = (vd[i] + vs[i] * ml) % mod;
		}

		vec[dst].second = (vec[dst].second + vec[src].second * ml) % mod;
	};
	auto sub = [&](int dst, int src, ll ml) { add(dst, src, (mod - ml) % mod); };
	auto mul = [&](int dst, ll ml) { add(dst, dst, (ml + mod - 1) % mod); };

	Loop (i,0,n) {
		debug {
			for (auto x : vec[i].first.vec)
				cerr << x << ' ';
			cerr << '\n';
		}
		mul(i, inv(vec[i].first[i]));
		Loop (j, i+1, n) {
			if (!vec[j].first.has(i))
				break;
			sub(j, i, vec[j].first[i]);
		}
	}

	LoopR (i,0,n) {
		LoopR (j,0,i) {
			if (!vec[j].first.has(i))
				break;
			sub(j, i, vec[j].first[i]);
		}
	}

	Loop (i,0,n)
		cout << vec[i].second << ' ';
	cout << '\n';
}

signed main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int t = 1;
	cin >> t;
	while (t--)
		solve();
}
0