M. Baby Ehab's Whining Chance

Codeforces

IDCF10288M

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Baby Ehab had just been stung by increasing subsequences in IOI, so he decided to make himself feel better about his skills. He chose an integer $n$, wrote down all integers from $1$ to $n$, and calculated the longest increasing subsequence like a true genius! Enter Baby Badawy again as envious as ever. Baby Badawy decided to play a trick on Baby Ehab. He replaced every integer in the sequence with the sum of its digits. Of course, Baby Ehab started crying. It was IOI all over again! So, his "babysitter" Laggy hired you to find the longest increasing subsequence of this sequence so that Baby Ehab would stop crying. Hurry up! You only have 300 minutes before Baby Ehab dies of dehydration. The only line contains a single integer $n$ $(1 <= n <= 10^(100000))$. Print the longest increasing subsequence required in the statement. ## Input The only line contains a single integer $n$ $(1 <= n <= 10^(100000))$. ## Output Print the longest increasing subsequence required in the statement. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $. A set $ T \subseteq \mathbb{Z}^+ $ is called *$ n $-ordinary* if: - $ \min(T) = 1 $, - $ \max(T) = n $, - For all $ x \in T $, $ x \mid n $, - $ T $ is closed under taking divisors: if $ x \in T $ and $ d \mid x $, then $ d \in T $. Let $ \mathcal{U}_n $ be the set of all $ n $-ordinary sets. **Objective** Compute: $$ S(n) = \sum_{T \in \mathcal{U}_n} \sum_{x \in T} x \mod 998244353 $$ **Constraints** $ 1 \le n \le 10^9 $

API Response (JSON)

{
  "problem": {
    "name": "M. Baby Ehab's Whining Chance",
    "description": {
      "content": "Baby Ehab had just been stung by increasing subsequences in IOI, so he decided to make himself feel better about his skills. He chose an integer $n$, wrote down all integers from $1$ to $n$, and calcu",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10288M"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Baby Ehab had just been stung by increasing subsequences in IOI, so he decided to make himself feel better about his skills. He chose an integer $n$, wrote down all integers from $1$ to $n$, and calcu...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $. A set $ T \\subseteq \\mathbb{Z}^+ $ is called *$ n $-ordinary* if:  \n- $ \\min(T) = 1 $,  \n- $ \\max(T) = n $,  \n- For all $ x \\in T $, $ x \\mid n $,  \n- $ T...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments