• محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

شاید باورش سخت باشد اما متن سوال به صورت صریح و عاری از داستان‌های تخیلی، در زیر آمده است:

برنامه‌ای بنویسید که با درنظرگرفتن دنباله‌ی اعداد صحیحa0,a1,,an1a_0,a_1,\cdots,a_{n-1} عدد طبیعی ll و عدد طبیعی kk تعداد زیردنباله‌های متوالی از b0,b1,,bl1b_0,b_1,\cdots,b_{l-1} را که حداقل kk عدد متمایز دارند، محاسبه کند. دنباله‌ی b0,b1,,bl1b_0,b_1,\cdots,b_{l-1} به صورت زیر ساخته می‌شود:

bi=a(i,mod,n)+in×n,(0il1)b_i = a_{(i , mod , n)} + \lfloor \frac{i}{n} \rfloor \times n , (0 \leq i \leq l-1)

ورودی

در سطر اول ورودی به ترتیب سه عدد طبیعی k,l,nk,l,n آمده است.

در سطر دوم ورودی nn عدد صحیح آمده است که اعداد دنباله‌‌ی a0,a1,,an1a_0,a_1,\cdots,a_{n-1} را نشان می‌دهند.

1n2 0001 \leq n \leq 2\ 000 1kl1091 \leq k \leq l \leq 10^9 nln \leq l

خروجی

در تنها سطر خروجی پاسخ مسئله را چاپ کنید.

زیر مسئله‌ها

زیرمسئله نمره محدودیت
۱ ۱۲ k,l1 000 000 k,l \le 1\ 000\ 000
۲ ۲۱ k=2 k = 2
۳ ۶۷ بدون محدودیت اضافی

مثال

ورودی نمونه ۱

3 6 4
1 2 3
Plain text

خروجی نمونه ۱

6
Plain text

ورودی نمونه ۲

3 6 4
1 4 7
Plain text

خروجی نمونه ۲

1
Plain text

ورودی نمونه ۳

3 10 1
1 1 1
Plain text

خروجی نمونه ۳

55
Plain text

ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.