CF1988F Heartbeat
Description
For an array $ u_1, u_2, \ldots, u_n $ , define
- a prefix maximum as an index $ i $ such that $ u_i>u_j $ for all $ ju_j $ for all $ j>i $ ;
- an ascent as an index $ i $ ( $ i>1 $ ) such that $ u_i>u_{i-1} $ .
You are given three cost arrays: $ [a_1, a_2, \ldots, a_n] $ , $ [b_1, b_2, \ldots, b_n] $ , and $ [c_0, c_1, \ldots, c_{n-1}] $ .
Define the cost of an array that has $ x $ prefix maximums, $ y $ suffix maximums, and $ z $ ascents as $ a_x\cdot b_y\cdot c_z $ .
Let the sum of costs of all permutations of $ 1,2,\ldots,n $ be $ f(n) $ . Find $ f(1) $ , $ f(2) $ , ..., $ f(n) $ modulo $ 998\,244\,353 $ .
Input Format
N/A
Output Format
N/A
Explanation/Hint
In the second example:
- Consider permutation $ [1,2,3] $ . Indices $ 1,2,3 $ are prefix maximums. Index $ 3 $ is the only suffix maximum. Indices $ 2,3 $ are ascents. In conclusion, it has $ 3 $ prefix maximums, $ 1 $ suffix maximums, and $ 2 $ ascents. Therefore, its cost is $ a_3b_1c_2=12 $ .
- Permutation $ [1,3,2] $ has $ 2 $ prefix maximums, $ 2 $ suffix maximums, and $ 1 $ ascent. Its cost is $ 6 $ .
- Permutation $ [2,1,3] $ has $ 2 $ prefix maximums, $ 1 $ suffix maximum, and $ 1 $ ascent. Its cost is $ 4 $ .
- Permutation $ [2,3,1] $ has $ 2 $ prefix maximums, $ 2 $ suffix maximums, and $ 1 $ ascent. Its cost is $ 6 $ .
- Permutation $ [3,1,2] $ has $ 1 $ prefix maximum, $ 2 $ suffix maximums, and $ 1 $ ascent. Its cost is $ 3 $ .
- Permutation $ [3,2,1] $ has $ 1 $ prefix maximum, $ 3 $ suffix maximums, and $ 0 $ ascents. Its cost is $ 3 $ .
The sum of all permutations' costs is $ 34 $ , so $ f(3)=34 $ .