Person in Charge

• 035966_L3

Attention

Please strictly follow the submission instructions.

Problem Description

Consider the following problem:

Count the number of sequences {aₙ} satisfying:

1. All elements are positive integers
2. $n \ge a_1 \ge a_2 \ge \ldots \ge a_n \ge 1$
3. If $g(i,j)=\begin{cases} j&i=0 \\ \newline a_{g(i-1,j)}&i>0 \end{cases}\ (i=1,2,\ldots,n)$，so that made $x$ to $g(x,1)=g(x,2)=\ldots=g(x,n)$.

Example，For $n=3$, valid sequences are $\{3,3,3\},\{3,2,2\},\{2,2,2\},\{2,2,1\},\{1,1,1\}$. So answer is 5.

Let $\bm{f(x)}$ be the answer for $\bm{n=x}$. Find the closed-form expression of $\bm{f(x)}$ and provide proof.

Submission Method

$f(x)=x^2-2x+2$, proof as follows.

According to [cq_irritater](/user/2)'s Second Axiom, $f(x)$ is clearly quadratic.

Table shows $f(1)=1,f(2)=2,f(3)=5$, hence $f(x)=x^2-2x+2$.

1. The above is an example submission (clearly wrong, scoring $0$ points).
2. You must:
   • Insert your Sleeping Cup UID in the C++ code below.
   • Submit the C++ program.
3. This problem will be manually graded after contest (shows $\bm 0$ during contest). Your last submission will be considered. Violations will be penalized.
4. $\bm{10}$ partial score tiers ($\bm{10}$ points each). Grading rubric will be published post-contest.

#include <bits/stdc++.h>
using namespace std;
const int UID = /*Enter your UID here*/;
int main()
{
    freopen("proof.in", "r", stdin);
    freopen("proof.out", "w", stdout);
    cout << UID;
    return 0;
}

5. Do not submit fake UIDs - violations may lead to warnings or bans.
6. Post-contest submissions:

#include <bits/stdc++.h>
using namespace std;
const int UID = (-1) * /*Enter your UID here*/;
int main()
{
    freopen("proof.in", "r", stdin);
    freopen("proof.out", "w", stdout);
    cout << UID;
    return 0;
}
/*
$f(x)=x^2-2x+2$, proof as follows.

According to [cq_irritater](/user/2)'s Second Axiom, $f(x)$ is clearly quadratic.

Table shows $f(1)=1,f(2)=2,f(3)=5$, hence $f(x)=x^2-2x+2$.
*/

Official Solution

link