تیم‌بندی کج


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

افراد ۱ تا nn تیم‌بندی شده‌اند و در یک صف قرار گرفته‌اند. به یک شیوه تیم بندی یک دنباله a1,a2,...,ana_1,a_2,...,a_n نسبت میدهیم به این شکل که به ترتیب عناصر دنباله را میسازیم:

  • در مرحله ii ام اگر فرد با شماره ii با فرد شماره jj هم‌تیمی بود به شکلی که i>ji>j aia_i را برابر aja_j قرار میدهیم.
  • در غیر این صورت aia_i را برابر مینیمم عدد طبیعی مانند xx قرار می‌دهیم که xx برابر هیچ کدام از اعداد a1,a2,...,ai1a_1,a_2,...,a_{i-1} نباشد.

یک دنباله a1,a2,...,ana_1,a_2,...,a_n به شما داده شده است که تضمین می‌شود تیم‌بندی‌ای وجود داره که دنباله‌اش برابر آن شود. تعداد تیم‌بندی‌‌هایی را بشمارید که دنباله‌هایشان از لحاظ لکسیکوگرافیکالی کمتر یا برابر دنباله aa باشد. چون ممکن است این عدد خیلی بزرگ باشد، باقی‌مانده آن را به 1 000 0071\ 000\ 007 حساب کنید.

ورودی🔗

در خط اول ورودی یک عدد nn داده شده است. در خط دوم دنباله a1,a2,...,ana_1,a_2,...,a_n داده شده است. 1n10 0001 \leq n \leq 10\ 000

خروجی🔗

باقی‌مانده تعداد تیم‌بندی‌های با شرایط گفته شده بر 1 000 0071\ 000\ 007 را در یک خط چاپ کنید.

زیر مسئله‌ها🔗

زیرمسئله نمره محدودیت
۱ ۳۰ n14n \le 14
۲ ۲۰ n100n \le 100
۳ ۲۰ n1 000n \le 1\ 000
۴ ۳۰ بدون محدودیت اضافی

مثال🔗

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

3
1 2 2
Plain text

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

4
Plain text

دنباله‌های معتبر:

  • 1111 1 1
  • 1121 1 2
  • 1211 2 1
  • 1221 2 2
  • 1231 2 3
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.