String Power STRPOW Solution

String Power STRPOW April Long Challenge 2021

Chef has been recently studying strings and probabilities and he came up with a problem for you.

Consider an alphabet with N characters (denoted by c1,c2,…,cN). For each valid i, the character ci has a power ai; the power of a string that contains only characters from this alphabet is the sum of their powers (if a character occurs multiple times, its power also occurs in the sum multiple times). For example, the power of a string c1c2c3 is a1+a2+a3 and the power of a string c1c2c1 is 2⋅a1+a2.

Also, for each valid i, you are given two parameters pi and Bi, where pi is a non-negative integer and Bi∈{0,1}. For an integer K, we can construct a random string S with length K in the following way:

Define R=∑i=1Npi.
First, each of the K characters of S is chosen independently. For each valid i and j, the i-th character of S is cj with probability pj/R.
Then, for each valid i, we compute the number of occurrences of ci in S and if the parity of this number of occurrences (i.e. its remainder modulo 2) is different from Bi, we discard the string S and try to construct a new random string S from the beginning.
Otherwise (if the parities of occurrences of all characters match the sequence B), we have constructed the random string S.
All parameters are chosen in such a way that there is at least one string we can generate without discarding it. In particular, R>0.
What is the expected value of the power of the constructed string S? You need to answer Q queries. In each query, you are given a different value of K and you should find the expected power.

For each query, it can be proved that the expected power can be represented as a fraction PQ, where P and Q are non-negative integers and Q is coprime with 998,244,353. You need to compute P⋅Q−1 modulo 998,244,353, where Q−1 denotes the multiplicative inverse of Q modulo 998,244,353.

The first line of the input contains a single integer N.
N lines follow. For each valid i, the i-th of these lines contains three space-separated integers ai, pi and Bi.
The next line contains a single integer Q.
Q lines follow. Each of these lines contains a single integer K describing a query.
For each query, print a single line containing one integer P⋅Q−1 modulo 998,244,353.

1≤ai≤4⋅108 for each valid i
0≤pi≤2,000 for each valid i
Bi∈{0,1} for each valid i
Subtask #1 (2 points, time limit 1 second): N,K≤15
Subtask #2 (8 points, time limit 1.5 seconds):

Subtask #3 (10 points, time limit 1.5 seconds): N,R≤400
Subtask #4 (80 points, time limit 2.5 seconds): original constraints

Example Input
1 1 0
2 2 1
Example Output
In the first query, we can only generate the one-character string c2. Therefore, the expected power is 2.

In the second query, we can generate the following strings:

c1c1c2 with power 4 and probability 2/14
c1c2c1 with power 4 and probability 2/14
c2c1c1 with power 4 and probability 2/14
c2c2c2 with power 6 and probability 8/14
The expected power is therefore 2⋅4+2⋅4+2⋅4+8⋅62+2+2+8=367=855,638,022.

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

1. Frog Sort Solution Codechef

2. Chef and Meetings Solution Codechef

3. Maximise Function Solution Codechef

4. Highest Divisor Solution Codechef

5. Cut the Cake Challenge Solution Codechef

6. Dream and the Multiverse Solution Codechef

7. Cell Shell Solution Codechef

8. Multiple Games Solution Codechef

9. Another Tree with Number Theory Solution Codechef

10. XOR Sums Solution Codechef

11. Prime Game Solution CodeChef

12. Team Name Solution Codechef

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS


Related :

Related :

Leave a Comment

4 × 4 =