اگر p_1, p_2, \cdots , p_n جایگشتی از اعداد 1 تا n باشد، جایگشت p^2 که آن را ابرجایگشت p مینامیم، یک جایگشت n^2 تایی است که به صورت زیر تعریف میشود:
دنبالهی q_i را برابر با p_1 + (i − 1) * n, p_2 + (i − 1) * n, \cdots , p_n + (i − 1) * n تعریف میکنیم، حال جایگشت p^2 برابر است با: q_{p_1}, q_{p_2},\cdots , q_{p_n} .
برای مثال ابرجایگشت 2 \ 3 \ 1 برابر است با 5 \ 6 \ 4 \ 8 \ 9 \ 7 \ 2 \ 3 \ 1.
برنامهای بنویسید که اندازهی دورهای گرافجایگشت یک ابرجایگشت را به عنوان ورودی بگیرد و تعداد جایگشتهای n تایی مانند p که گرافجایگشت p^2 به این شکل است را در خروجی چاپ کند. با توجه به اینکه این مقدار ممکن است بزرگ باشد، باقیماندهی آن را بر 10^9 + 7 محاسبه کنید.
با تشکر از آقای مهندس و خانم دکتر!
در ابتدای خروجی گرافجایگشت یکی از جایگشتهای p که p^2 جایگشت دادهشده در ورودی باشد را به همان فرمت ورودی چاپ کنید. در اولین سطر عدد m و در m سطر بعدی در هر سطر دو عدد c_i و l_i را چاپ کنید که نشان میدهد گرافجایگشت p، به تعداد c_i تا دور به طول l_i دارد. دقت کنید که c_1/1 + c_2/2 + \cdots+ c_m/m باید برابر n باشد و هیچ دو l_iای با یکدیگر برابر نباشند. در صورت وجود چندین جواب هر کدام از آنها را میتوانید چاپ کنید.
در سطر آخر خروجی باقیماندهی تعداد جایگشتهایی که گراف ابر جایگشت آنها مطابق ورودی است را بر 10^9 + 7 چاپ کنید.
نمرهدهی این سوال به این شکل است که اگر جایگشت ارائه شده اشتباه باشد نمرهای به شما تعلق نمیگیرد، در صورتی که جایگشت ارائه شده درست باشد ولی تعداد جایگشتهای با این شرایط را اشتباه چاپ کرده باشید، نیمی از نمره به شما تعلق میگیرد و تنها در صورتی نمرهی کامل میگیرید که هم جایگشت ارائه شده و هم تعداد جایگشتها درست باشد. (به ازای هر زیرمساله)
ورودی نمونه | خروجی نمونه |
---|---|
2 3 1 1 4 2 | 2 1 1 1 2 3 |
1 4 4 4 | 1 1 4 6 |
5 9 2 2 3 3 8 4 2 6 2 12 | 3 1 2 1 3 1 4 15120 |