خرگوش‌ها


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

ابواسحاق پس از خواندن تمام نامه‌ها، به یک دعوت‌نامه بَر خورد. او که بسیار کنجکاو شده بود به آدرس داخل دعوت‌نامه رفت و سَر از جزیرهٔ آدم‌خوارها درآورد! آن‌ها ابواسحاق را تهدید کردند که اگر می‌خواهد او را نخورند، باید جای خرگوش‌های جزیره را برایشان پیدا کند. او هم که خیلی ترسیده بود، از شما کمک خواست تا جای خرگوش‌ها را پیدا کنید. سوال آدم خوارها به صورت زیر است:

تعدادی خرگوش روی محور xx ها ایستاده‌اند. خرگوش‌ها با اعداد ۱ تا nn شماره‌گذاری شده‌اند و خرگوش شماره ii ابتدا در موقعیت مکانی aia_i قرار دارد. یک عملیات قرینه‌سازی روی خرگوش شماره ii به صورت زیر انجام می شود:

  • با احتمال برابر، یکی از خرگوش‌های i+1i+1 یا i1i-1 انتخاب می‌شود (اندیس‌ها دایره ای هستند؛ به عبارت دیگر اگر عملیات روی خرگوش شماره ۱ انجام شود، یکی از خرگوش‌های 22 یا nn انتخاب می‌شوند).

  • موقعیت خرگوش شماره ii نسبت به خرگوش انتخاب شده قرینه می‌شود.

آدم‌خوارها به ما یک ترتیب از عملیات‌های قرینه‌سازی را می‌دهند و ما kk بار پشت سر هم و به همین ترتیب، این عملیات‌ها را انجام می‌دهیم. حال شما باید به ازای هر خرگوش باقیمانده امیدریاضی مکانش را نسبت به 109+710^9 + 7 به دست آورید.

ورودی🔗

در خط اول ورودی، تعداد خرگوش‌ها، nn می‌آید. سپس در خط دوم، دنباله a1,a2,...,ana_1 , a_2 , ... , a_n موقعیت مکانی اولیه خرگوش‌ها می آیند. در خط بعد، دو عدد mm و kk ورودی داده می‌شوند. در خط آخر، دنباله عملیات‌ها، b1,b2,...,bmb_1 , b_2 , ... , b_m ورودی داده می‌شود.

3n200 000 3 \le n \le 200\ 000 0ai109+6 0 \le a_i \le 10^9 + 6 1m200 000 1 \le m \le 200\ 000 1k1018 1 \le k \le 10^{18}

خروجی🔗

در خروجی یک دنباله به طول nn، شامل امید ریاضی مکان نهایی خرگوش‌ها باقیمانده بر 109+710^9 + 7 را چاپ کنید.

ورودی نمونه ۱🔗

3
1 2 3
3 2
2 1 3
Plain text

خروجی نمونه ۱🔗

4
5
6
Plain text

ورودی نمونه ۲🔗

4
1 0 1 0
2 3
2 3
Plain text

خروجی نمونه ۲🔗

1
0
1
0
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.