Palindrome Basis (Codeforces 1673C)
Tags: Math, number theory

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. Formally, you need to find the number of distinct multisets of positive palindromic integers the sum of which is equal to $$$n$$$.Since the answer can be quite large, print it modulo $$$10^9+7$$$.

Input: The first line of input contains a single integer $$$t$$$ ($$$1\leq t\leq 10^4$$$) denoting the number of testcases.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.

Output: For each testcase, print a single integer denoting the required answer modulo $$$10^9+7$$$.

Note: For the first testcase, there are $$$7$$$ ways to partition $$$5$$$ as a sum of positive palindromic integers:   $$$5=1+1+1+1+1$$$  $$$5=1+1+1+2$$$  $$$5=1+2+2$$$  $$$5=1+1+3$$$  $$$5=2+3$$$  $$$5=1+4$$$  $$$5=5$$$ 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.

Sample Inputs:
2
5
12

Sample Outputs:
7
74

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
ans = []
mod = pow(10, 9) + 7
x = []
l = 4 * pow(10, 4) + 5
for i in range(1, l):
    s = list(str(i))
    ok = 1
    for j in range(len(s)):
        if not s[j] == s[-(j + 1)]:
            ok = 0
            break
    if ok:
        x.append(i)
dp = [0] * l
dp[0] = 1
for i in x:
    for j in range(l - i):
        dp[i + j] += dp[j]
        dp[i + j] %= mod
for _ in range(t):
    n = int(input())
    ans0 = dp[n]
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import math, sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000007
mod2 = 998244353
n = 40000
l = [i for i in range(1, n + 1) if str(i) == str(i)[::-1]]
dp = [0] * (n + 1)
dp[0] = 1
for i in l:
    for j in range(i, n + 1):
        dp[j] = (dp[j] + dp[j - i]) % mod1
for _ in range(I()):
    print(dp[I()] % mod1)

Solution (Python):
""""""
import io, os, sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
output = sys.stdout.write
DEBUG = os.environ.get('debug') not in [None, '0']
if DEBUG:
    from inspect import currentframe, getframeinfo
    from re import search

def debug(*args):
    if not DEBUG:
        return
    frame = currentframe().f_back
    s = getframeinfo(frame).code_context[0]
    r = search('\\((.*)\\)', s).group(1)
    vnames = r.split(', ')
    var_and_vals = [f'{var}={val}' for (var, val) in zip(vnames, args)]
    prefix = f'{currentframe().f_back.f_lineno:02d}: '
    print(f"{prefix}{', '.join(var_and_vals)}")
INF = float('inf')
MOD = 10 ** 9 + 7
MAX = 4 * 10 ** 4
dp = [0] * (MAX + 1)
dp[0] = 1
for p in range(1, MAX + 1):
    sp = str(p)
    if sp != sp[::-1]:
        continue
    for n in range(p, MAX + 1):
        dp[n] = (dp[n] + dp[n - p]) % MOD

def solve(N):
    return dp[N]

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        out = solve(N)
        print(out)
if __name__ == '__main__':
    main()