結果

問題 No.2305 [Cherry 5th Tune N] Until That Day...
ユーザー square1001square1001
提出日時 2023-05-14 22:32:07
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,276 bytes
コンパイル時間 1,255 ms
コンパイル使用メモリ 88,804 KB
実行使用メモリ 166,220 KB
最終ジャッジ日時 2024-05-09 08:13:36
合計ジャッジ時間 12,641 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
166,220 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef CLASS_MODINT
#define CLASS_MODINT

#include <cstdint>

template <std::uint32_t mod>
class modint {
private:
	std::uint32_t n;
public:
	modint() : n(0) {};
	modint(std::int64_t n_) : n((n_ >= 0 ? n_ : mod - (-n_) % mod) % mod) {};
	static constexpr std::uint32_t get_mod() { return mod; }
	std::uint32_t get() const { return n; }
	bool operator==(const modint& m) const { return n == m.n; }
	bool operator!=(const modint& m) const { return n != m.n; }
	modint& operator+=(const modint& m) { n += m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator-=(const modint& m) { n += mod - m.n; n = (n < mod ? n : n - mod); return *this; }
	modint& operator*=(const modint& m) { n = std::uint64_t(n) * m.n % mod; return *this; }
	modint operator+(const modint& m) const { return modint(*this) += m; }
	modint operator-(const modint& m) const { return modint(*this) -= m; }
	modint operator*(const modint& m) const { return modint(*this) *= m; }
	modint inv() const { return (*this).pow(mod - 2); }
	modint pow(std::uint64_t b) const {
		modint ans = 1, m = modint(*this);
		while (b) {
			if (b & 1) ans *= m;
			m *= m;
			b >>= 1;
		}
		return ans;
	}
};

#endif // CLASS_MODINT

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
using mint = modint<998244353>;

class edge {
public:
	int to; mint weight;
	edge() : to(-1), weight(mint()) {}
	edge(int to_, const mint& weight_) : to(to_), weight(weight_) {}
};

int main() {
	// step #1. read input (without queries) & make graph
	int N;
	cin >> N;
	N += 1;
	vector<int> P(N, -1);
	for (int i = 1; i < N; i++) {
		cin >> P[i];
	}
	vector<vector<edge> > G(N);
	for (int i = 1; i < N; i++) {
		int x;
		cin >> x;
		G[P[i]].push_back(edge(i, mint(x)));
	}

	auto solve = [&](int K, int mark) {
		// step #2. compute values used in dynamic programming
		vector<int> depth(N);
		depth[0] = 0;
		vector<mint> prob(N);
		prob[0] = 1;
		vector<bool> flag(N, false);
		flag[mark] = true;
		for (int i = 0; i < N; i++) {
			if (!G[i].empty()) {
				mint allmul = 0;
				for (edge e : G[i]) {
					allmul += e.weight;
				}
				allmul = prob[i] * allmul.inv();
				for (edge e : G[i]) {
					depth[e.to] = depth[i] + 1;
					prob[e.to] = e.weight * allmul;
					if (flag[i]) {
						flag[e.to] = true;
					}
				}
			}
		}
		vector<mint> v1(N + 1), v2(N + 1);
		for (int i = 0; i < N; i++) {
			if (G[i].empty()) {
				v1[depth[i] + 1] += prob[i];
				if (flag[i]) {
					v2[depth[i] + 1] += prob[i];
				}
			}
		}

		// step #3. dynamic programming
		vector<mint> dp1(K + 1), dp2(K + 1);
		dp1[0] = 1;
		dp2[0] = 0;
		for (int i = 1; i <= K; i++) {
			for (int j = 1; j <= N && j <= i; j++) {
				dp1[i] += dp1[i - j] * v1[j];
				dp2[i] += dp2[i - j] * v1[j] + dp1[i - j] * v2[j];
			}
		}

		// step #4. calculate answer
		mint answer = 0, s1 = 0, s2 = 0;
		for (int i = N - 1; i >= 0; i--) {
			s1 += v1[i + 1];
			s2 += v2[i + 1];
			if (K >= i) {
				answer += dp2[K - i] * s1 + (i >= depth[mark] ? dp1[K - i] * s2 : mint(0));
			}
		}
		if (mark == 0) {
			answer -= 1;
		}

		return answer;
	};

	// step #6. process queries
	int Q;
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		int a, k;
		cin >> a >> k;
		mint answer = solve(k, a);
		cout << answer.get() << endl;
	}
	
	return 0;
}
0