Too Many Exams

H. Too Many Exams

No Submission Yet

Problem Statement

It's the end of the school year, and Eggag is ready for happy summertime! However, in order not to go to summer school, Eggag must pass at least one of his \(K\) classes. LHS uses a system of \(N\) different letter grades labeled from \(1\) to \(N\), with \(N\) being the ultimate passing grade to not go to summer school.

To earn a new letter grade, Eggag must take exams for his classes. The school gives different exams depending on your current letter grade, and an exam for letter grade \(i\) takes \(b_i\) hours (Note that this doesn't depend on which class, but only Eggag's current grade in that class). Once Eggag takes the exam, he gains a new letter grade in that class based on his exam score. However, because LHS's curriculum is WAY TOO HARD for anybody's mental health, Eggag effectively guesses on all of his exams. Eggag's probability of getting letter grade \(i\) is proportional to nonnegative integer \(a_i\), which means that Eggag has a probability of \(\frac{a_i}{\sum^N_{j=1}{a_j}}\) to achieve letter grade \(i\) after taking an exam. This does not depend on the class or his previous grade.

There is no class with letter grade \(N\) initially. The number of Eggag's classes with letter grade \(i\) is \(c_i\) for \(1 \leq i < N\), and \(\sum{c_i} = K\). Eggag may choose to take whichever classes' exams in whatever order he likes, and he may retake the same class' exams multiple times (Although the exams' length will change as his letter grade changes). Please help him find the expected least number of hours for taking exams before he can enjoy summer.

It can be proved that, under the constraint of this problem, the answer is a rational number \(\frac{p}{q}\) where \(p\) and \(q\) are mutually coprime non-negative integers and \(q\) is positive and not divisible by \(998244353\). Let \(r\) be the unique modular inverse of \(q\). Print the value \(p \cdot r \mod 998244353\).

Additional Notes

Time Limit:
C++: 2.5 seconds
Java, Python: 5 seconds
Memory Limit: 256mb


\(2 \leq N \leq 2 \cdot 10^5\)
\(0 \leq b_i,c_i \leq 10^9\)
\(0 < a_N,\sum{c_i} = K \)
\(1 \leq \sum{a_i} < 998244353\)
Furthermore, the second test case guarantees \(K = 1\), and the third test case guarantees \(K = 2\).

Input Format

The first line contains \(2\) integers \(N\) and \(K\).
The second line contains \(N\) integers, the ith number being \(a_i\)
The third line contains \(N - 1\) integers, the ith number being \(b_i\)
The fourth line contains \(N - 1\) integers, the ith number being \(c_i\)

Output Format

Output the expected least number of hours for taking exams modulo \(998244353\)

Sample Input

4 2
3 5 2 6
2 5 4
0 1 1

Sample Output


Sample Explanation

It can be proved that the minimum expected number of hours is \(\frac{21}{2} \equiv 21 \cdot 2^{-1} \equiv 499122187 \mod 998244353\)

Credit: CodeTiger

Contact Us
LIT Discord Server