codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1673C.md (1862B)


      1 Source: https://codeforces.com/problemset/problem/1673/C
      2 
      3 C. Palindrome Basis
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a positive integer $n$. Let's call some positive integer $a$ without leading zeroes palindromic if it remains the same after reversing the order of its digits. Find the number of distinct ways to express $n$ as a sum of positive palindromic integers. Two ways are considered different if the frequency of at least one palindromic integer is different in them. For example, $5=4+1$ and $5=3+1+1$ are considered different but $5=3+1+1$ and $5=1+3+1$ are considered the same.
     22 
     23 Formally, you need to find the number of distinct multisets of positive palindromic integers the sum of which is equal to $n$.
     24 
     25 Since the answer can be quite large, print it modulo $10^9+7$.
     26 
     27 Input
     28 
     29 The first line of input contains a single integer $t$ ($1\leq t\leq 10^4$) denoting the number of testcases.
     30 
     31 Each testcase contains a single line of input containing a single integer $n$ ($1\leq n\leq 4\cdot 10^4$) — the required sum of palindromic integers.
     32 
     33 Output
     34 
     35 For each testcase, print a single integer denoting the required answer modulo $10^9+7$.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 2
     43 
     44 5
     45 
     46 12
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 7
     53 74
     54 ```
     55 
     56 Note
     57 
     58 For the first testcase, there are $7$ ways to partition $5$ as a sum of positive palindromic integers:
     59 
     60 * $5=1+1+1+1+1$
     61 * $5=1+1+1+2$
     62 * $5=1+2+2$
     63 * $5=1+1+3$
     64 * $5=2+3$
     65 * $5=1+4$
     66 * $5=5$
     67 
     68 For the second testcase, there are total $77$ ways to partition $12$ as a sum of positive integers but among them, the partitions $12=2+10$, $12=1+1+10$ and $12=12$ are not valid partitions of $12$ as a sum of positive palindromic integers because $10$ and $12$ are not palindromic. So, there are $74$ ways to partition $12$ as a sum of positive palindromic integers.