No.1875 Flip Cards
ytqm3
ぷら
shino16
MtSakaProblem Statement
Kame-kun is playing with $N$ types of cards. There are $C_i$ cards of type $i \ (1 \le i \le N)$, each with $A_i$ written in black on the front and $B_i$ written in red on the back.
Here, the score is defined as the product of the numbers written on the front faces of all cards.
For each $k=1,2,\ldots,M$, find the following value modulo $998244353$.
There are $(\sum_i C_i)^k$ ways to perform the following operation $k$ times; the sum, over all of them, of the score after the operations are finished (added at 22:03)
Choose one card. If the color of the text on the front of the card is black, flip it over so that the side with the red text becomes the front.
Here, cards of the same type are also considered distinct from each other in the operation.
Input
$N$ $M$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_N$ $B_N$ $C_N$
- All inputs are integers
- $1 \le N,M \le 10^5$
- $1 \le A_i, B_i, C_i \le 998244352$
Output
Output $M$ lines. On the $i$-th line, output the answer for $k=i$.
Sample
Sample 1
Input
2 2 1 2 1 2 1 1
Output
5 9
We explain the case $k=2$. Let us call the card of type $1$ card $1$, and the card of type $2$ card $2$.
If the operations are performed in the order card $1$, card $1$, the score is $2\times 2=4$;
in the order card $1$, card $2$, the score is $2\times 1=2$;
in the order card $2$, card $1$, the score is $2\times 1=2$;
in the order card $2$, card $2$, the score is $1\times 1=1$. Therefore, the sum of the scores is $4+2+2+1=9$.
Sample 2
Input
2 3 3 1 4 1 5 9
Output
3753 159381 6171489
Sample 3
Input
3 5 265 358 97932384 626 433 83279502 884 197 16939937
Output
405902234 486977455 905998771 23125155 250629615
Don't forget to take the answer modulo $998244353$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。