Subtask 1

Quay lui để tính.

Subtask 2

Do ~t = 1~; ~a_i \le 15~, và ~LCM(1;2;...;15)~ khá bé nên ta hoàn toàn có thể sử dụng quy hoạch động.

Gọi ~dp(i,j)~ là xét tới vị trí ~i~ và thu được bội chung nhỏ nhất là ~j~, thì có bao nhiêu dãy con.

Đáp án là ~dp(n,k)~.

Subtask 3

Do ~k~ được xây dựng từ các số nguyên tố phân biệt với lũy thừa ~1~, dễ thấy đây là một gợi ý để đưa về bài toán bitmask.

Với mỗi ~a_i~, ta sẽ đưa nó về dạng ~mask~ (xem các số nguyên tố của ~k~ có xuất hiện trong thừa số nguyên tố của ~a_i~ hay không).

Nhận xét quan trọng: phép ~LCM~ bây giờ có thể được tính bằng phép ~OR~ thông qua các ~mask~.

Vậy ta đưa về một bài toán ~dp~ xử dụng ~bitwise~ đơn giản. Với ~S(G)~ được biểu diễn bằng ~mask~, ~f(G) = all \oplus mask~ (~all~ là ~mask~ của ~k~).

Subtask 4

Tiếp tục cải tiến ~subtask~ ~3~, giờ công việc của ta là tính nhanh được số tập có ~mask~ đúng bằng ~all~. Biết rằng, ~mask~ của một tập được tính bằng ~OR~ của các phần tử trong đó.

Để làm được điều đó, trước tiên ta gọi ~dp(M)~ là số phần tử có ~mask~ là ~subset~ của ~M~, ta sẽ dễ dàng tính được nó trong ~3^m~.

Vậy số tập có ~mask~ thuộc ~subset~ của ~M~ sẽ được tính bằng ~F(M) = 2^{dp(M)}~.

Nhưng đó chưa phải thứ ta muốn, cái ta cần là ~mask~ của các tập phải đúng bằng ~all~. Và để làm được điều này, ta chỉ cần dùng bao hàm loại trừ là được.

Subtask 5

Với việc các số nguyên tố của số ~k~ không còn chỉ có mũ là ~1~ nữa, ta nhận thấy cách lưu ~mask~ như ~subtask~ trước sẽ không dùng được.

Nhưng với điều kiện ~\sum x_i \le 20~, ta thấy rẳng mình vẫn cần một cách lưu ~mask~ khác.

Giả sử:

• ~k = 2^3 \times 3^2 \times 5^3~.
• Ta có số ~a_i~ = ~2^4 \times 3^1 \times 5 \times 7~.
• Ta sẽ đặt ~mask_i = 11110100~ (biểu diễn theo bit 0 → bit lớn nhất).

Điều này tương đương việc ta trải dãy ~k~ ra thành tích các số nguyên tố (có thể trùng nhau), và gán ~bit~ cho chúng.

Với cách lưu này thì ta có thể chứng minh được rằng phép ~LCM~ vẫn bằng với phép ~OR~.

Như vậy bài toán giờ đang giống hệt với ~subtask~ ~4~, ngoại trừ việc ta không thể tính mảng ~F~ trong ~3^{20}~ được.

Vậy nên ta sẽ cần sử dụng tới ~DP~ ~SOS~ để tính tổng của các ~submask~ trong ~2^{20} \times 20~.

Subtask 6

Do ta cần tính với mọi ~mask~, vậy nên điều ta cần cải tiến lúc này là pha bao hàm loại trừ ở cuối, bởi nếu ta bao hàm loại trừ cho tất cả các ~mask~, độ phức tạp sẽ là ~O(3^{20})~.

Đến đây, ta lại sẽ cải tiến bằng ~DP~ ~SOS~, kĩ thuật này khá giống ~VOI~ ~21~, bài ~3~. Bởi việc bao hàm loại trừ của một ~mask~ bản chất là tính tổng của các ~submask~ của nó, chỉ có điều ta sẽ quyết định dấu của phép tính dựa vào tính chẵn lẻ của ~mask~ đó.

Hoặc, một cách cải tiến cũng mang hiệu quả tương tự nhưng ngắn gọn hơn, đó là làm ngược pha ~DP~ ~SOS~. Bởi như ta đã biết, ~DP~ ~SOS~, bản chất là gộp các tập có dạng "bằng ~mask~" vào cho các hàm "thuộc con của ~mask~". Ở đây ta lại cần ngược lại, từ thuộc con về với dạng bằng, nói cách khác chỉ cần dùng ~SOS~ ngược là được!

Nhận xét: Đây là một tư duy khá hay trong các bài toán về ~submask~ và đặc biệt liên quan tới các toán tử như ~OR~ và ~AND~.