Title DTQG 25-26 BAI TAP.docx ✅

Input: gồm một dòng là xâu ký tự S có độ dài xâu |S| ≤ 10 5 ; Output: ghi số lượng xâu con trong xâu S tạo thành số đặc biệt. Vi dụ: Input Output Giải thích 2910 3 Có 3 số đặc biệt là 291, 2910, 0. Giới hạn:  50% số test ứng với độ dài xâu |S| < 300;  30% số test ứng với độ dài xâu |S| < 10 3 ;  20% số test ứng với độ dài xâu |S| < 10 5 . Câu 3. SLIME Slime Rumiru là một cô bé rất thích chơi với slime. Hôm nay, cô quyết định đến một cửa hàng để mua một số con về chơi. Trong cửa hàng có trưng bày n con slime, con thứ i từ trái sang phải có kích thước a i . Rumiru muốn mua một số con slime và gộp một số cặp lại với nhau để tạo thành ít nhất một con có kích thước đúng bằng s, quy tắc gộp như sau: Chọn hai con slime bất kỳ có kích thước bằng nhau và gộp chúng lại thành một con mới có kích thước bằng tổng kích thước của hai con cũ. Hãy giúp Rumiru đếm số cách mua thoả mãn điều kiện. Biết rằng, hai cách mua được xem là khác nhau khi tồn tại một con slime được mua ở cách này nhưng không được mua ở cách còn lại. Dữ liệu  Dòng đầu tiên chứa hai số nguyên n và s (1 ≤ n ≤ 2 × 10 5 , 1 ≤ s ≤ 5 × 10 3 ) lần lượt là số lượng con slime và kích thước slime mong muốn.  Dòng tiếp theo chứa n số nguyên a 1 , a 2 , . . . , a n (1 ≤ a i ≤ s) là kích thước của các con slime Kết quả: Một số nguyên duy nhất là phần dư số cách mua khi chia cho 10 9 + 7. Hạn chế  Subtask 1 (20% số điểm): n ≤ 20.  Subtask 2 (30% số điểm): n ≤ 2 × 10 3 .  Subtask 3 (10% số điểm): a 1 = a 2 = . . . = a n .  Subtask 4 (40% số điểm): Không có ràng buộc gì thêm. Ví dụ: Input Output Giải thích 3 2 1 1 2 5 Có 5 cách mua thoả mãn là: {a 3 }, {a 1 , a 2 }, {a 1 , a 3 }, {a 2 , a 3 }, {a 1 , a 2 , a 3 }. 5 4 1 1 2 3 4 18 Câu 4. STORE Cửa hàng Vào năm 2112, tất cả công việc được chuyên môn hóa, năng suất lao động tăng cực kỳ cao, dẫn tới dư thừa của cải đủ cho gấp đôi dân số vào lúc đó. Vì thế mọi người làm theo năng lực, và hưởng theo nhu cầu. Vì công việc chuyên môn hóa tới mức độ cao nhất, nên trong việc kinh doanh buôn bán cũng vậy. Ở một khu phố nọ, có n cửa hàng xếp kề nhau, đánh số từ 1 tới n theo chiều từ đầu tới cuối phố. Mỗi cửa hàng chỉ bán một mặt hàng mang bản sắc riêng của mình, có giá là a i . Để chống cạnh tranh, các mặt hàng phục vụ các nhu cầu khác nhau, và giá cả cũng khác nhau. Để thuận tiện cho người mua hàng dễ tìm kiếm, các chủ tịệm đã cùng nhau thỏa thuận lại vị trí bán hàng, để giá của

1 7 1122 2 7 4086 2 5 6863 1 8 1532 1 8 825 1 2 1890 2 1 10000  Người thứ tư sẽ mua tại các cửa hàng 1, 2, 3, 4, 5, 6