+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *علی برای بهبود کار شرکت می‌خواهد چند نفر از اعضای شرکت که می‌توانند سوال زیر را حل کنند انتخاب کند و آن‌ها را برای آموزش پیشرفته آماده کند... تربچه که خیلی دوست دارد آموزش‌های پیشرفته را ببیند می‌خواهد این سوال را حل کند... به او کمک کنید تا این کار را انجام دهد...* برای هر عدد طبیعی فرض کنید $P_n$ مجموعه همه دنباله‌هایی از اعداد طبیعی باشد که جمع اعضای این دنباله برابر $n$ است. به عبارت دیگر: $$P_n = \{ (a_1a_2a_3\dots a_m) | a_1+a_2+a_3+\dots+a_m=n\}$$ اکنون ترب می‌خواهد عبارت زیر را محاسبه کند. $$ \sum_{(a_1a_2a_3\dots a_m) \in P_n} {a_1}^k{a_2}^k{a_3}^k\dots{a_m}^k$$ به ترب کمک کنید تا این عبارت را محاسبه کند چون ممکن است پاسخ شما بسیار عدد بزرگی باشد باقی‌مانده آن را به پیمانه $10^9+7$ حساب کنید. # ورودی ورودی تنها شامل یک خط است که در آن دو عدد طبیعی $n$ و $k$ با فاصله از هم آمده است. $$1 \le k\le 100,1 \le n\le 10^9$$ # خروجی در تنها سطر خروجی پاسخ مسئله را به پیمانه $10^9+7$ چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 1 1 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 4 2 ``` ## خروجی نمونه ۲ ``` 63 ``` تمام اعضای مجموعه $P_4$ عبارت است از: $$P_4=\{ (1,1,1,1), (2,1,1), (1,2,1), (1,1,2), (2,2), (3,1), (1,3), (4) \} $$ بنابراین حاصل مجموع فوق برابر است با: $$ 1 + 4 + 4 + 4 + 16 + 9 + 9 + 16 = 63$$ # قسمت آموزشی در این قسمت راهنمایی‌های سوال، به مرور اضافه می‌شود. مشکلات‌تان در راستای حل سوال را می‌توانید از بخش ["سوال بپرسید"](https://quera.ir/contest/clarification/19378/) مطرح کنید. <details class="blue"> <summary> راهنمایی ۱ </summary> اولین نکته‌ای که توجه به آن برای حل مسئله ضروری می‌باشد، این است که افرازهایمان ترتیب دارند و برای مثال افراز `1 2` با افراز `2 1` فرق دارد. حال بر اساس این نکته می‌توان دریافت که تعداد افرازهای ترتیب‌دار عدد $n$ برابر $2^{n - 1}$ می‌باشد چرا که می‌توانیم $n$ توپ در یک ردیف در نظر بگیریم و هر افراز را با یک حالت دیوار گذاشتن در $n - 1$ جایگاه خالی بین‌ توپ‌ها متناظر کنیم. حال برای عبارت جواب، مسئله‌ای ترکیبیاتی تعریف می‌کنیم و تلاش می‌کنیم تا با شمارش مضاعف، آن را به روش دیگری محاسبه کنیم: در یک ردیف، $n$ جعبه متوالی با شماره ۱ تا $n$ داریم. می‌خواهیم آن‌ها را بلوک‌بندی کنیم و در هر بلوک، به ازای همه رنگ‌های ۱ تا $k$، دقیقا یک توپ با آن رنگ را در یکی از جعبه‌های این بلوک قرار دهیم. اگر ترتیب قرار دادن توپ‌ها در جعبه‌ها اهمیتی نداشته باشد، به چند طریق این کار ممکن است؟ </details> <details class="blue"> <summary>راهنمایی ۲</summary> برای حل مسئله مطرح شده در انتهای راهنمایی قبل، از برنامه‌نویسی پویا استفاده می‌کنیم یا به عبارت دیگر $dp$ می‌زنیم :) ابتدا به تعریف $dp$ می‌پردازیم. $dp[i][j]$ یعنی تعداد روش‌های چیدن توپ‌ها در $i$ جعبه اول به گونه‌ای که بلوک آخرمان برای تکمیل شدن،‌ به $j$ توپ رنگی دیگر نیاز داشته باشد. دقت کنید که تعداد بلوک‌ها برایمان اهمیتی ندارد و نه در مولفه و نه در پاسخ هر خانه آرایه، به آن اشاره‌ای نمی‌کنیم. حالت پایه که تقریبا واضح است، $dp[0]0] = 1$. برای اپدیت کردن یک استیت، بر روی تعداد توپ‌های رنگی خانه $i$ام حالت می‌بندیم. به ازای همه $r$هایی که $j \le r \le k$، از $dp[i - 1][r]$ اپیدت می‌شوم و ضریب این اپدیت هم برابر حاصل انتخاب $j$ از $r$ می‌باشد چرا که قرار است از $r$ توپ رنگی باقی‌مانده در مرحله قبل، $j$ تا را برای ادامه بلوک انتخاب کنیم و بقیه را در جعبه $i$ ام قرار دهیم. همچنین یک حالت دیگر هم وجود دارد و آن هم اینکه خانه $i$ام اولین خانه بلوک جدید باشد که در این حالت $dp[i][j]$ باید از $dp[i - 1][0]$ با ضریب $j$ از $k$ اپدیت شود. با توجه به راه‌حل تعداد خانه‌های آرایه $dp$ که باید پر شوند، $nk$ می‌باشد و برای اپدیت کردن هر خانه هم $O(k)$ عملیات انجام می‌دهیم. بنابراین پیچیدگی زمانی راه‌حل فعلی از $O(nk^2)$ می‌باشد. </details> <details class="blue"> <summary>راهنمایی ۳</summary> حال که بلدیم برای مسئله $dp$ دو بعدی مناسبی تعریف کنیم که هر سطر آن، فقط از سطر قبلی و به صورت خطی با ضرایب آپدیت می‌شود، می‌توانیم از ماتریس برای حل مسئله استفاده کنیم. به این صورت که یک ماتریس یک بعدی به طول $k + 1$ را به عنوان پایه در نظر می‌گیریم و از یک ماتریس دو بعدی $(k + 1) \times (k + 1)$ برای اپدیت کردن آن استفاده می‌کنیم، به این صورت که اگر ماتریس دو بعدی ما در ماتریس یک بعدی ما که نشان‌دهنده مقادیر خانه‌های سطر $i$ام است ضرب شود، حاصل ماتریس یک بعدی خواهد شد که مقادیر سطر $i + 1$ را داراست. ساختن این ماتریس نیز بر اساس ضرایب اپدیت $dp$ است و تعدادی انتخاب و به علاوه یک خواهد بود. حال می‌دانیم که مقادیر سطر صفر را در ماتریس پایه‌ بریزیم، برای داشتن سطر پایانی باید $n$ بار در ماتریس اپدیت ضرب شویم و از آن‌جایی که ضرب ماتریس به صورت بالا خاصیت شرکت‌پذیری دارد، ابتدا ماتریس اپدیت را در $O(k^3lg_n)$ به توان $n$ می‌رسانیم و سپس حاصل را در ماتریس پایه ضرب می‌کنیم تا سطر $n$ام $dp$ به دست آید و خانه اول آن یعنی $dp[n][0]$ پاسخ مسئله ما خواهد بود. </details>

افراز توان دار

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

علی برای بهبود کار شرکت می‌خواهد چند نفر از اعضای شرکت که می‌توانند سوال زیر را حل کنند انتخاب کند و آن‌ها را برای آموزش پیشرفته آماده کند... تربچه که خیلی دوست دارد آموزش‌های پیشرفته را ببیند می‌خواهد این سوال را حل کند... به او کمک کنید تا این کار را انجام دهد...

برای هر عدد طبیعی فرض کنید $P_n$ مجموعه همه دنباله‌هایی از اعداد طبیعی باشد که جمع اعضای این دنباله برابر $n$ است. به عبارت دیگر: $P_n = \{ (a_1a_2a_3\dots a_m) | a_1+a_2+a_3+\dots+a_m=n\}$ اکنون ترب می‌خواهد عبارت زیر را محاسبه کند. $\sum_{(a_1a_2a_3\dots a_m) \in P_n} {a_1}^k{a_2}^k{a_3}^k\dots{a_m}^k$ به ترب کمک کنید تا این عبارت را محاسبه کند چون ممکن است پاسخ شما بسیار عدد بزرگی باشد باقی‌مانده آن را به پیمانه $10^9+7$ حساب کنید.

ورودی🔗

ورودی تنها شامل یک خط است که در آن دو عدد طبیعی $n$ و $k$ با فاصله از هم آمده است. $1 \le k\le 100,1 \le n\le 10^9$

خروجی🔗

در تنها سطر خروجی پاسخ مسئله را به پیمانه $10^9+7$ چاپ کنید.

مثال🔗

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

1 1

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

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

4 2

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

تمام اعضای مجموعه $P_4$ عبارت است از: $P_4=\{ (1,1,1,1), (2,1,1), (1,2,1), (1,1,2), (2,2), (3,1), (1,3), (4) \}$ بنابراین حاصل مجموع فوق برابر است با: $1 + 4 + 4 + 4 + 16 + 9 + 9 + 16 = 63$

قسمت آموزشی🔗

در این قسمت راهنمایی‌های سوال، به مرور اضافه می‌شود. مشکلات‌تان در راستای حل سوال را می‌توانید از بخش "سوال بپرسید" مطرح کنید.

راهنمایی ۱

اولین نکته‌ای که توجه به آن برای حل مسئله ضروری می‌باشد، این است که افرازهایمان ترتیب دارند و برای مثال افراز 1 2 با افراز 2 1 فرق دارد. حال بر اساس این نکته می‌توان دریافت که تعداد افرازهای ترتیب‌دار عدد $n$ برابر $2^{n - 1}$ می‌باشد چرا که می‌توانیم $n$ توپ در یک ردیف در نظر بگیریم و هر افراز را با یک حالت دیوار گذاشتن در $n - 1$ جایگاه خالی بین‌ توپ‌ها متناظر کنیم.

حال برای عبارت جواب، مسئله‌ای ترکیبیاتی تعریف می‌کنیم و تلاش می‌کنیم تا با شمارش مضاعف، آن را به روش دیگری محاسبه کنیم:

در یک ردیف، $n$ جعبه متوالی با شماره ۱ تا $n$ داریم. می‌خواهیم آن‌ها را بلوک‌بندی کنیم و در هر بلوک، به ازای همه رنگ‌های ۱ تا $k$ ، دقیقا یک توپ با آن رنگ را در یکی از جعبه‌های این بلوک قرار دهیم. اگر ترتیب قرار دادن توپ‌ها در جعبه‌ها اهمیتی نداشته باشد، به چند طریق این کار ممکن است؟

راهنمایی ۲

برای حل مسئله مطرح شده در انتهای راهنمایی قبل، از برنامه‌نویسی پویا استفاده می‌کنیم یا به عبارت دیگر $dp$ می‌زنیم :) ابتدا به تعریف $dp$ می‌پردازیم. $dp[i][j]$ یعنی تعداد روش‌های چیدن توپ‌ها در $i$ جعبه اول به گونه‌ای که بلوک آخرمان برای تکمیل شدن،‌ به $j$ توپ رنگی دیگر نیاز داشته باشد. دقت کنید که تعداد بلوک‌ها برایمان اهمیتی ندارد و نه در مولفه و نه در پاسخ هر خانه آرایه، به آن اشاره‌ای نمی‌کنیم.

حالت پایه که تقریبا واضح است، $dp[0]0] = 1$ .

برای اپدیت کردن یک استیت، بر روی تعداد توپ‌های رنگی خانه $i$ ام حالت می‌بندیم. به ازای همه $r$ هایی که $j \le r \le k$ ، از $dp[i - 1][r]$ اپیدت می‌شوم و ضریب این اپدیت هم برابر حاصل انتخاب $j$ از $r$ می‌باشد چرا که قرار است از $r$ توپ رنگی باقی‌مانده در مرحله قبل، $j$ تا را برای ادامه بلوک انتخاب کنیم و بقیه را در جعبه $i$ ام قرار دهیم.

همچنین یک حالت دیگر هم وجود دارد و آن هم اینکه خانه $i$ ام اولین خانه بلوک جدید باشد که در این حالت $dp[i][j]$ باید از $dp[i - 1][0]$ با ضریب $j$ از $k$ اپدیت شود.

با توجه به راه‌حل تعداد خانه‌های آرایه $dp$ که باید پر شوند، $nk$ می‌باشد و برای اپدیت کردن هر خانه هم $O(k)$ عملیات انجام می‌دهیم. بنابراین پیچیدگی زمانی راه‌حل فعلی از $O(nk^2)$ می‌باشد.

راهنمایی ۳

حال که بلدیم برای مسئله $dp$ دو بعدی مناسبی تعریف کنیم که هر سطر آن، فقط از سطر قبلی و به صورت خطی با ضرایب آپدیت می‌شود، می‌توانیم از ماتریس برای حل مسئله استفاده کنیم.

به این صورت که یک ماتریس یک بعدی به طول $k + 1$ را به عنوان پایه در نظر می‌گیریم و از یک ماتریس دو بعدی $(k + 1) \times (k + 1)$ برای اپدیت کردن آن استفاده می‌کنیم، به این صورت که اگر ماتریس دو بعدی ما در ماتریس یک بعدی ما که نشان‌دهنده مقادیر خانه‌های سطر $i$ ام است ضرب شود، حاصل ماتریس یک بعدی خواهد شد که مقادیر سطر $i + 1$ را داراست. ساختن این ماتریس نیز بر اساس ضرایب اپدیت $dp$ است و تعدادی انتخاب و به علاوه یک خواهد بود.

حال می‌دانیم که مقادیر سطر صفر را در ماتریس پایه‌ بریزیم، برای داشتن سطر پایانی باید $n$ بار در ماتریس اپدیت ضرب شویم و از آن‌جایی که ضرب ماتریس به صورت بالا خاصیت شرکت‌پذیری دارد، ابتدا ماتریس اپدیت را در $O(k^3lg_n)$ به توان $n$ می‌رسانیم و سپس حاصل را در ماتریس پایه ضرب می‌کنیم تا سطر $n$ ام $dp$ به دست آید و خانه اول آن یعنی $dp[n][0]$ پاسخ مسئله ما خواهد بود.