Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۳۳:عملی نهایی سوم:سوال ۲

مجاور خوب (Good Adjacent)

امتیاز یک دنباله برابر تعداد جفت خانه‌های مجاوری است که مجموع آنها برابر k می‌شود. به عنوان مثال اگر k=3 باشد، امتیاز دنباله 1,2,3,0,2 برابر 2 است.

به شما عدد صحیح نامنفی k و یک دنباله n تایی از اعداد داده می‌شود. شما باید تعداد جایگشت‌های از این دنباله که امتیازشان برابر i می‌شود را به ازای هر i از 0 تا n1 بدست آورید. چون اعداد جواب ممکن است بزرگ شود کافی است که باقی‌مانده تقسیم هر عدد را بر 998244353 چاپ کنید.

توجه کنید که اعداد مساوی قابل تمایز هستند.

ورودی

در خط اول دو عدد صحیح n و k به ترتیب می‌آیند.

در خط دوم n عدد صحیح می‌آیند که نشان‌دهنده دنباله ورودی است.

خروجی

در تنها خط خروجی n عدد چاپ کنید که به ترتیب برابر با تعداد جایگشت‌های دنباله با امتیاز 0,1,,n1، باقی مانده بر 998244353 است.

زیرمسئله‌ها

  • زیرمسئله اول (۴ نمره): n10.
  • زیرمسئله دوم (۱۲ نمره): تعداد اعداد متمایز حداکثر دو است.
  • زیرمسئله سوم (۱۷ نمره): تعداد اعداد متمایز حداکثر سه است.
  • زیرمسئله چهارم (۲۳ نمره): n500
  • زیرمسئله پنجم (۴۴ نمره): بدون محدودیت اضافی

محدودیت‌ها

  • 1n5000
  • 0k109
  • اعداد دنباله نامنفی و کمتر از 109 هستند.

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
5 3
1 2 1 2 1
0 24 36 48 12

ابزار صفحه