Mam pytanie. Zapisywałem się do grupy C jako początkujący, a mimo to widzę zadanie dla grupy A oraz B. To oznacza, że również muszę je wykonać?

Nie lepiej by było po prostu wymagać weryfikacji konta przed umożliwieniem postowania na forum?

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.

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.

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)?

Actually, wikipedia się zgadza
Hydepark – specjalny dział występujący na forach internetowych, czatach i innych serwisach internetowych, pozwalający na wolną dyskusję nieograniczoną żadnym tematem przewodnim.

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

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.

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

Czym jest prefiks?

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

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.

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.

Dzięki. Czyli to dość skomplikowane.

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.