Jak należało rozwiązać zadanie LIC?

Ja zrobiłem 4-wymiarowe dp[pozycja][czy w tym prefiksie liczby gdzieś daliśmy cyfrę mniejszą od tej w podanej liczbie?][nww][suma w prefiksie modulo 2520]. Robisz dla l i r i odejmujesz:) Ewentualnie wchodzi też dp[-||-][-||-][maska][-||-], tylko musisz patrzeć jakie nww tworzy dany subset.

Dzięki. Czyli to dość skomplikowane.

Bez programowania dynamicznego się raczej nie obeszło, no chyba żeby ktoś sobie przeliczył wszystkie przypadki na początku.
Ja miałem tablicę z ilością liczb Potyczkowa dla każdego prefiksu po 3 wymiarach: [mod 2520][pozycja końcowa prefiksu][nww użytych cyfr]. Cały myk w tym że krótsze prefiksy da się policzyć na podstawie dłuższych. Np. zawartość tabeli dla pierwszego prefiksu jest sumą zawartości dla pozostałych:

prefiks wymiary
2*** [2000][3][2]
------------------------
21** [2100][2][2]
22** [2200][2][2]
23** [2300][2][6]
24** [2400][2][4]
25** [2500][2][10] – tu na pewno będzie 0, bo liczba by musiałaby być podzielna przez 10, a nie może zawierać cyfry 0
26** [80][2][6]
27** [180][2][14]
28** [280][2][8]
29** [380][2][18]

W głównej pętli sumowałem zawartość tablicy dla najdłuższych prefiksów pasujących do liczb pomiędzy l a r.

Serafin: a po co wymiar [czy w tym prefiksie liczby gdzieś daliśmy cyfrę mniejszą od tej w podanej liczbie?]? U mnie działało bez tego.

Dodałem ten wymiar, żeby mieć pewność, że nie przekroczy podanej liczby.

Czym jest prefiks?

Ogólnie, to początek napisu. W tym przypadku, z tego co rozumiem, to np. 27 w napisie 27**.

Ogólnie to na coś takiego mówi się "dynamik po cyfrach" (digit dp). Jeśli ktoś nigdy czegoś takiego nie robił, to na początek polecam zrobić sobie zadania:

1) Dane jest K <= 18. Policz liczby podzielne przez 3 o długości K.
2) Dane jest K <= 18. Policz liczby podzielne przez 7 o długości K.
3) Dane jest słowo T długości maksymalnie 50. Policz słowa z literek a-z, które spełniają trzy warunki: jest leksykograficznie mniejsze niż T, długość taka sama jak T; jest więcej samogłosek niż spółgłosek.
3) Dane są liczby S <= 200 oraz N <= 10^18. Policz te liczby w przedziale [1, N], których suma cyfr wynosi S.

Tu jest fajny artykuł o tej technice: https://codeforces.com/blog/entry/53960

A czy ktoś miał rozwiązanie hybrydowe? Brute-force gdy r - l < 10^6, a dynamik w pozostałych przypadkach? Bo dla ograniczonego zakresu r - l chyba zdarzało się, że brute force był szybszy (tak bym zgadywał po czasach na swoim pierwszym zgłoszeniu).

Swoją drogą czy testy będą dostępne (bo w poprzednich latach chyba były)?

Jeszcze gwoli wyjaśnienia: prefiks to początkowa część liczby dla której liczymy ilość liczb Potyczkowa (* oznacza nieznaną cyfrę). Zawartość tablicy odpowiada na pytanie ile jest liczb Potyczkowa zaczynających się od tego prefiksu. Sęk w tym że jest wiele prefiksów odpowiadających jednej komórce w tej tabeli, i dla nich wszystkich ilość liczb Potyczkowa będzie ta sama, więc wystarczy to raz policzyć i za kolejnym razem tylko sczytać wartość. Np. prefiksy 126*** i 126126*** odpowiadają komórce o wymiarach [0 = 126000 mod 2520 = 126126000 mod 2520][3 (ilość niewiadomych cyfr)][6 (nww cyfr)], i liczb Potyczkowa dla obu prefiksów jest 27. Wszystkich komórek może być w tablicy maksymalnie 2520*19*48 =~ 2,3 miliona i taka będzie złożoność algorytmu w najgorszym przypadku. A skąd te wymiary? Liczba Potyczkowa musi się dzielić przez wszystkie swoje cyfry, więc przez ich nww (najmniejszą wspólną wielokrotność), zatem liczba Potyczkowa modulo nww cyfr musi być 0. No a ponieważ nww wszystkich możliwych cyfr (nww(1,2,3,4,5,6,7,8,9) = 2520) jest podzielne przez nww każdego podzbioru tych cyfr, to wystarczy sprawdzać czy liczba Potyczkowa modulo 2520 dzieli się przez nww cyfr, co znacząco zmniejsza ilość przypadków do sprawdzenia.

Testy są już dostępne w zakładce Tests. Mi opisany algorytm działał w czasie 0,01s dla najgorszego przypadku, więc hybryda by się mijała z celem.