- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
شرکت آقای مهندس از معدود شرکت‌های عمرانی است که قادر به «تخریب طبقهای» ساختمان‌های قدیمی است. «تخریب طبقهای» یک ساختمان، به معنای تخریب طبقه‌های آن ساختمان به ترتیب از بالاترین طبقه تا پایین‌ترین طبقه‌ی آن است. در واقع در این روش کل ساختمان با استفاده از ماده‌های انفجاری به یک‌باره تخریب نمی‌شود.
گاهی این شرکت باید چندین ساختمان را تخریب کند و برای همین از چند گروه تخریب‌گر برای خراب کردن آن‌ها استفاده می‌کند. می‌دانیم هر گروه در هر روز قادر به تخریب بالاترین طبقه‌ی یک ساختمان است. به یک مجموعه از ساختمان‌ها $(k,d)$-تخریب‌پذیر می‌گوییم، اگر بتوان با $k$ گروه تخریب‌گر و در حداکثر $d$ روز تمامی ساختمان‌های آن را تخریب کرد. یعنی بعد از این مدت هیچ طبقهای از آن‌ها باقی نمانده باشد. دقت کنید که برای انجام یک پروژه‌ی تخریب، در ابتدای هر روز به هر یک از گروه‌ها، یکی از ساختمانهایی که هنوز کاملا تخریب نشده (تعداد طبقه‌هایش بیشتر از صفر است) محول می‌شود و در پایان آن روز بالاترین طبقه‌ی آن ساختمان تخریب می‌شود. می‌توان به بعضی از گروه‌ها در ابتدای یک روز هیچ ساختمانی اختصاص نداد. هم‌چنین در یک روز هیچ دو گروهی نباید مشغول تخریب یک ساختمان شوند.
بنابراین با در نظر گرفتن این محدودیت‌ها، بعد از گذشت یک روز، تعداد ساختمانهایی که مورد تخریب قرار می‌گیرند حداکثر $k$ تا هستند و از هر کدام از آن‌ها حداکثر یک طبقه تخریب می‌شود.
حال آقای مهندس تمامی ساختمان‌های شهر را بررسی و $n$ تا از آن‌ها را به عنوان ساختمان‌های فرسوده‌‌ی شناسایی کرده است. او از شما خواسته تا برنامه‌ای بنویسید که به پرسش‌هایی از قبیل
«تعداد زیر‌مجموعه‌های ناتهی از ساختمان‌های فرسوده که $(k,d)$-تخریب‌پذیر هستند، چند تاست؟» پاسخ دهد.
با توجه به این‌که پاسخ‌ها ممکن است عدد بزرگی باشند، کافی است باقی‌مانده‌ی این مقدار را بر $10^9 + 7$ محاسبه کنید.
ورودی
در سطر اول ورودی به ترتیب دو عدد طبیعی $n$، تعداد ساختمان‌های فرسوده، و $q$، تعداد پرسش‌های آقای مهندس، آمده است.
سطر دوم ورودی شامل دنباله‌ی
$$ a_1, a_2, ..., a_n $$
آمده‌است که نشان‌دهنده‌ی تعداد طبقات ساختمان‌های فرسوده است.
در هر یک از $q$ سطر بعدی به ترتیب دو مقدار $k$ و $d$ مربوط به پرسش $i$-ام آمده است. $$1 \le n \le 400$$
$$1\le q \le 200\ 000$$
$$1\le a_{1},a_{2},...,a_{n}\le 400$$
$$1\le d\le 400^2$$
$$1\le k\le n$$
خروجی
خروجی شامل $q$ سطر است که در سطر $i$-ام از آن پاسخ به پرسش $i$-ام آقای مهندس آمده است.
زیرمسئله‌ها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۱۰ | $ k = 1 $ |
| ۲ | ۱۰ | $q \le 1\ 000$, $ n \le 15$ |
| ۳ | ۳۰ | $,a_i \le50$ $ n \le 50$ |
| ۴ | ۵۰ | بدون محدودیت اضافی |
مثال
ورودی نمونه
5 5
1 2 3 4 5
1 2
2 3
3 4
4 5
5 1
خروجی نمونه
2
7
15
31
1
(۲۴امین دوره المپیاد کامپیوتر - آزمون چهارم - ۱۳۹۳/۰۶/۱۲)
ارسال پاسخ برای این سؤال