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

به‌جای شمردن مستقیم جایگشت‌ها، روی مجاورت‌های خوب تمرکز کنید. دو عضو با مقدارهای \(x\) و \(y\) یک مجاورت خوب می‌سازند اگر و تنها اگر \(x+y=k\). اعضای برابر را هم متمایز فرض کنید؛ یعنی جایگشت‌ها روی \(n\) شیء برچسب‌دار هستند.

یک گراف \(G\) روی \(n\) رأس بسازید؛ هر رأس یکی از اعضای ورودی است و بین دو رأس یال می‌گذاریم اگر مجموع مقدارهایشان برابر \(k\) باشد. حالا مسئله می‌خواهد برای هر \(i\)، تعداد جایگشت‌هایی را بشمارد که دقیقاً \(i\) یال از \(G\) به‌صورت دو رأس مجاور ظاهر شده‌اند.

اول مسئله‌ی ساده‌تر را حل کنید: برای هر \(m\)، تعداد حالت‌هایی را بشمارید که یک مجموعه‌ی مشخص از \(m\) یال‌های خوب را مجبور کرده‌ایم در جایگشت مجاور باشند. بعداً از این شمارش به جواب دقیقاً \(i\) مجاورت خوب می‌رسیم.

اگر مجموعه‌ای از یال‌های اجباری در یک جایگشت قابل ظاهر شدن باشد، درجه‌ی هر رأس در آن مجموعه حداکثر \(2\) است. همچنین نباید دور داشته باشیم. بنابراین یال‌های اجباری باید اجتماع چند مسیر رأس‌ناهمپوش باشند.

اگر مجموعه‌ی اجباری \(m\) یال داشته باشد و این یال‌ها \(c\) مسیر غیرتهی بسازند، هر مسیر را به یک بلوک فشرده کنید. هر مسیر دو جهت دارد، و بعد از فشرده‌سازی تعداد بلوک‌ها برابر \(n-m\) است. پس سهم چنین مجموعه‌ای برابر است با \[ 2^c (n-m)!. \]

برای هر \(m\)، مقدار \(P_m\) را این‌گونه تعریف کنید: \[ P_m=\sum 2^c, \] که جمع روی همه‌ی مجموعه‌های معتبر \(m\)-یالی است و \(c\) تعداد مسیرهای غیرتهی آن مجموعه است. آن‌گاه تعداد زوج‌های \((\pi,S)\) که \(S\) یک مجموعه‌ی \(m\)-تایی از مجاورت‌های خوبِ ظاهرشده در \(\pi\) است برابر می‌شود با \[ T_m=P_m(n-m)!. \]

اگر \(A_j\) تعداد جایگشت‌هایی باشد که دقیقاً \(j\) مجاورت خوب دارند، هرکدام از آن‌ها در \(T_m\) به تعداد \(\binom{j}{m}\) شمرده می‌شوند. پس \[ T_m=\sum_{j=m}^{n-1}\binom{j}{m}A_j. \]

با وارونگی دوجمله‌ای داریم: \[ A_i=\sum_{m=i}^{n-1}(-1)^{m-i}\binom{m}{i}T_m. \] پس کافی است همه‌ی مقدارهای \(P_m\) را حساب کنیم.

گراف \(G\) ساختار ساده‌ای دارد. مقدار \(x\) فقط می‌تواند با مقدار \(k-x\) یال بسازد. بنابراین رأس‌ها به مؤلفه‌هایی از نوع جفت مقدارهای مکمل تقسیم می‌شوند.

اگر \(x\neq k-x\)، بین همه‌ی رأس‌های با مقدار \(x\) و همه‌ی رأس‌های با مقدار \(k-x\) یال داریم و داخل هر طرف یالی نیست. پس این مؤلفه یک گراف کامل دوبخشی است: \[ K_{a,b}, \] که \(a=\operatorname{cnt}(x)\) و \(b=\operatorname{cnt}(k-x)\).

اگر \(x=k-x\)، یعنی \(2x=k\)، همه‌ی رأس‌های با این مقدار به هم وصل‌اند. پس این مؤلفه یک گراف کامل است: \[ K_c, \] که \(c=\operatorname{cnt}(x)\).

برای هر مؤلفه یک چندجمله‌ای بسازید: \[ F(z)=\sum_m P_m z^m. \] چون مؤلفه‌ها مستقل‌اند، چندجمله‌ای کل برابر حاصل‌ضرب چندجمله‌ای‌های مؤلفه‌هاست.

در گراف کامل \(K_c\)، اگر \(m\) یال انتخاب شده باشد و این یال‌ها \(r\) مسیر بسازند، تعداد رأس‌های استفاده‌شده برابر \(m+r\) است. سهم این حالت برابر است با \[ ©_{m+r}\frac{(m-1)!}{(r-1)!(m-r)!r!}, \] که در آن \[ ©_t=c(c-1)\cdots(c-t+1). \]

پس برای مؤلفه‌ی \(K_c\)، ضریب \(z^m\) برابر است با \[ \sum_{r=1}^{\min(m,c-m)} ©_{m+r}\frac{(m-1)!}{(r-1)!(m-r)!r!}, \] و ضریب \(z^0\) برابر \(1\) است.

در نظر بگیرید $(x)_y = x \times (x-1) \times (x-2) \times \dots \times (x-i+1)$

برای گراف کامل دوبخشی \(K_{a,b}\)، از چندجمله‌ای کمکی زیر استفاده کنید: \[ M(t)=\sum_{i\ge 0}\frac{(a)_i(b)_i}{i!}t^i. \] همچنین تعریف کنید: \[ M_1(t)=\sum_{i\ge 0}\frac{(a-1)_i(b-1)_i}{i!}t^i. \]

برای مؤلفه‌ی \(K_{a,b}\)، چندجمله‌ای موردنیاز برابر است با \[ F(t)=M(t)^2-abt^2M_1(t)^2. \] ضریب \(t^m\) در این چندجمله‌ای همان \(P_m\) برای این مؤلفه است.

برای پیاده‌سازی، همه‌ی چندجمله‌ای‌ها را فقط تا درجه‌ی \(n-1\) نگه دارید. ضرب ساده‌ی چندجمله‌ای‌ها با بریدن درجه‌های بزرگ‌تر از \(n-1\) کافی است و کل زمان را در حد \[ O(n^2) \] نگه می‌دارد.

فاکتوریل‌ها و معکوس فاکتوریل‌ها را از قبل پیمانه‌ای حساب کنید تا بتوانید سریع مقدارهای \[ \binom{n}{r} \qquad\text{و}\qquad (n)_r=\frac{n!}{(n-r)!} \] را به‌دست آورید. پیمانه برابر است با \[ 998244353. \]

بعد از به‌دست آوردن چندجمله‌ای کل \[ P(z)=\sum_m P_mz^m, \] ابتدا \[ T_m=P_m(n-m)! \] را حساب کنید و سپس با رابطه‌ی وارونگی \[ A_i=\sum_{m=i}^{n-1}(-1)^{m-i}\binom{m}{i}P_m(n-m)! \] جواب‌های نهایی را به‌دست آورید.

خروجی باید شامل \[ A_0,A_1,\ldots,A_{n-1} \] باشد. در تمام مراحل، منفی‌شدن مقدارها را با اضافه‌کردن پیمانه اصلاح کنید.