No.2575 Almost Increasing Sequence
Note
This is a score-based problem, but there is a maximum score, and the intended solution can achieve the maximum score.
However, the execution time limit of this problem is strict, so if you aim for the maximum score, using a fast language is strongly recommended.
The writer's and tester's solutions are both written in C++, and their execution times are 4024 ms and 673 ms, respectively.
Problem Statement
First, a non-negative integer $K$ is given, and the sequence $(A_1, A_2, A_3, \dots )$ is defined as follows.
- $A_n$ : the sum, over all permutations with $n$ elements whose longest decreasing subsequence has length $3$, of the length of the longest increasing subsequence raised to the power $K$, modulo $998244353$
Choose one positive integer $N$ not greater than $30000$, and find $A_n$ for each positive integer $n$ not greater than $N$.
Scoring
Your score for each test case is $N$ points. There are $20$ test cases in total, and the sum of the scores of all test cases is the score of the submission.
However, if the output is invalid, it is judged as WA, and the score of a submission that receives a verdict other than AC on one or more test cases is $0$ points. Invalid output refers to the following.
- The output does not follow the output format
- The output content is incorrect
The final ranking is determined by the highest score obtained during the contest, and no rejudging, system tests, or the like are planned after the contest ends.
Constraints
- $0 \leq K \leq 10^9$
- All inputs are given as integers
Input
$K$
Output
$N$
$A_1\ A_2 \dots A_{N}$
Sample
Sample 1
Input
100
Output
4 0 0 1 954786991
There is no permutation of length $2$ or less whose longest decreasing subsequence has length $3$.
The only permutation of length $3$ whose longest decreasing subsequence has length $3$ is $(3, 2, 1)$, and the length of the longest increasing subsequence of this permutation is $1$, so $A_3= 1^{100}=1$.
There are $9$ permutations of length $4$ whose longest decreasing subsequence has length $3$: $(1, 4, 3, 2), (2, 4, 3, 1), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 2, 1), (4, 1, 3, 2), (4, 2, 1, 3),(4, 2, 3, 1),(4, 3, 1, 2)$. In all of them the length of the longest increasing subsequence is $2$, so $A_4 \equiv 9 \times 2^{100} \equiv 954786991 \pmod {998244353}$.
For this test case, submitting this answer would earn $4$ points.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
hotman78
noshi91