Editorial for Game with Subsets

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Analiz ve Çözüm Yolu

Bir sayı tüm \(D\) (\(1 \le D \le 10\)) lere ancak ve ancak \(2520 = 9\cdot 8 \cdot 7 \cdot 5\) 'e bölünebiliyorsa bölünür. Bu problem iki boyutlu dinamik programlama yaklaşımı kullanılarak çözülebilir: ilk boyut (K) işlenmiş tamsayıların sayısı ve ikinci boyut (R) mod 2520'de bir altdizi toplamı.

Sorunun cevabı, toplamı mod 2520'de R'ye eşit olacak şekilde ilk K elemandan gelen altdizilerin sayısıdır.

Analysis and Guide for Solution

A number is divisible by all \(D\) (\(1 \le D \le 10\)) if and only if it is divisible by \(2520 = 9\ cdot 8 \cdot 7 \cdot 5\). The problem can be solved using a two dimensional dynamic programming approach: the first dimension (K) is the number of processed integers and the second dimension (R) is a subset sum modulo 2520. The value of the dynamic programming state is the number of subsets from the first K elements such that its sum modulo 2520 is equal to R.