Daxil edilmiş çoxluqlar#7033
Petrik yaxınlarda çoxluqlar və onların daxil edilməsi haqqında məlumat əldə etdi. O, S_0 \supset S_1 \supset S_2 \supset \ldots \supset S_n ardıcıllığı ilə maraqlanır, burada hər bir növbəti element əvvəlkinin alt çoxluğudur və S_0 müəyyən sonlu çoxluqdur \{a_1, a_2, \ldots, a_m\}.
Petrik qeyd etdi ki, hər bir daxil edilmiş çoxluğa tam ədəd H(S) = \sum_{a_k \in S} 2^{k-1} uyğunlaşdırıla bilər. Beləliklə, H(S_0) = 2^m - 1, H(\emptyset) = 0.
Petrik təsadüfi olaraq ədəd seçdi: h_1, h_2, , h_n. O, maraqlanır: H(S_1) \equiv h_1 \pmod{41}, H(S_2) \equiv h_2 \pmod{41}, , H(S_n) \equiv h_n \pmod{41} şərtini ödəyən fərqli daxil edilmiş çoxluqlar dəstləri S_1, S_2, , S_n neçə dənədir? Təəssüf ki, Petrik hesabdan çaşdı, buna görə sizdən kömək istəyir.
Birinci sətir iki tam ədəd və (1 \leq n \leq 5, 1 \leq m \leq 20) ehtiva edir.
İkinci sətir tam ədəd h_1, h_2, , h_n ehtiva edir, hər biri şərti ödəyir: 0 \leq h_k \leq 40.
Axtarılan daxil edilmiş çoxluqların sayını çıxarın. Məlumdur ki, bu, 10^{18}-i keçmir.
Testlər 1–3 üçün izah:
Yalnız bir variant mövcuddur: S_1 = \{a_1, a_2, a_3\}, S_2 = S_3 = \{a_1, a_2\}. H(S_1) = 7, H(S_2) = H(S_3) = 3.
Belə bir daxil edilmiş çoxluqlar kombinasiyası mövcud deyil.
H(\{a_1, a_2\}) = 2^{1-1} + 2^{2-1} = 3, H(\{a_3, a_4, a_6\}) = 2^2 + 2^3 + 2^5 = 4 + 8 + 32 = 44 = 41 + 3, H(\{a_1, a_3, a_5, a_7\}) = 2^0 + 2^2 + 2^4 + 2^6 = 1 + 4 + 16 + 64 = 85 = 2 \cdot 41 + 3, H(\{a_2, a_3, a_4, a_5, a_6, a_7\}) = 2^1 + 2^2 + 2^3 + 2^4 + 2^5 + 2^6 = 2 + 4 + 8 + 16 + 32 + 64 = 126 = 3 \cdot 41 + 3.
Nümunə 1
Nümunə 2
Nümunə 3
Nümunə 4