Good Digit DP problem

Правка en2, от simp_pro, 2022-08-17 20:57:12

You are given N. Find number of pairs of integers x, y such that

1 <= x < y <= N and sumOfDigits(x) > sumOfDigits(y)

Constraints:

N <= 10^100 and is given as a string.

Output answer modulo 1e9+7

I don't remember the sign of inequality properly, it might be sumOfDigits(x) < sumOfDigits(y). I read about digit DP to solve this but I cannot find any approach.

How to solve this?

Теги help, problem, solve

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский simp_pro 2022-08-17 20:57:12 75 Tiny change: ' it might sumOfDigi' -> ' it might be sumOfDigi'
en1 Английский simp_pro 2022-08-17 09:03:54 344 Initial revision (published)