به جای جمع زدن مستقیم روی همه‌ی جایگشت‌ها، یک جایگشت تصادفی یکنواخت در نظر بگیر. اگر \(X\) تعداد کل امتیازها در این جایگشت باشد، جواب مسئله برابر است با \[ n! \cdot \mathbb{E}[X]. \] پس کافی است امید ریاضی تعداد امتیازها را پیدا کنیم.

در هر لحظه فقط بیشینه‌ی قدرت مؤثر زندانی‌هایی که تا الان وارد شده‌اند مهم است. زندانی جدید فقط وقتی امتیاز می‌گیرد که قدرت فعلی‌اش از این بیشینه بیشتر باشد.

زندانی‌هایی را که قدرت اولیه‌ی برابر دارند در یک گروه قرار بده. فرض کن قدرت‌های متمایز به ترتیب صعودی برابر باشند با \[ v_1 < v_2 < \cdots < v_m, \] و تعداد زندانی‌های با قدرت \(v_i\) را با \(c_i\) نشان بدهیم.

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

برای هر گروه، متغیر تصادفی \(X_i\) را تعریف کن که اگر گروه \(i\) امتیاز بگیرد برابر \(1\)، وگرنه برابر \(0\) باشد. پس داریم \[ X = \sum_{i=1}^{m} X_i \] و بنابراین \[ \mathbb{E}[X] = \sum_{i=1}^{m} \Pr(X_i = 1). \] پس کافی است مقدار \[ p_i = \Pr(X_i = 1) \] را برای همه‌ی گروه‌ها حساب کنیم.

برای گروه \(i\)، فقط زندانی‌هایی با قدرت حداقل \(v_i\) می‌توانند مانع امتیاز گرفتن آن شوند. پس مقدار زیر را تعریف کن: \[ s_i = \sum_{j=i}^{m} c_j. \] این یعنی تعداد زندانی‌هایی که قدرتشان حداقل \(v_i\) است.

فعلاً اثر زیاد شدن قدرت بعد از امتیاز گرفتن را نادیده بگیر. در این حالت، گروه \(i\) دقیقاً وقتی امتیاز می‌گیرد که اولین زندانی در میان همه‌ی زندانی‌های با قدرت حداقل \(v_i\)، از خود گروه \(i\) باشد.

چون جایگشت تصادفی است، اولین زندانی در میان این \(s_i\) زندانی به طور یکنواخت یکی از آن‌هاست. پس احتمال اینکه از گروه \(i\) باشد برابر است با \[ \frac{c_i}{s_i}. \]

یک حالت را نباید بشماریم: اگر اولین زندانی کل جایگشت از گروه \(i\) باشد، قبل از او کسی نیست و امتیاز نمی‌گیرد. احتمال این حالت برابر است با \[ \frac{c_i}{n}. \] پس سهم پایه‌ی گروه \(i\) برابر است با \[ \frac{c_i}{s_i} - \frac{c_i}{n}. \]

حالا اثر افزایش قدرت را برگردان. اگر زندانی‌ای با قدرت \(u\) امتیاز بگیرد، قدرت مؤثرش به \(u+1\) تبدیل می‌شود. پس تنها گروهی که می‌تواند روی گروه \(i\) اثر اضافی بگذارد، گروهی با قدرت \[ v_i - 1 \] است.

اگر \[ v_{i-1}+1 \neq v_i, \] گروه قبلی حتی بعد از امتیاز گرفتن هم به قدرت \(v_i\) نمی‌رسد. پس در این حالت همان سهم پایه کافی است.

اگر \[ v_{i-1}+1 = v_i, \] ممکن است گروه \(i-1\) قبلاً امتیاز گرفته باشد و قدرت مؤثر یکی از زندانی‌هایش به \(v_i\) رسیده باشد. این اتفاق می‌تواند حالتی را که برای گروه \(i\) خوب شمرده بودیم خراب کند.

احتمال اینکه گروه \(i-1\) امتیاز گرفته باشد برابر \(p_{i-1}\) است. در صورت رخ دادن این اتفاق، همان حالت‌هایی از گروه \(i\) خراب می‌شوند که اولین زندانی در میان قدرت‌های حداقل \(v_i\)، از گروه \(i\) باشد. احتمال این بخش برابر است با \[ \frac{c_i}{s_i}. \] پس مقدار اضافه‌ای که باید کم شود برابر است با \[ p_{i-1}\cdot \frac{c_i}{s_i}. \]

بنابراین رابطه‌ی اصلی این است: \[ p_i = \frac{c_i}{s_i} - \frac{c_i}{n} - \delta_i p_{i-1}\frac{c_i}{s_i}, \] که در آن $ \delta_i = 1$ اگر $ v_{i-1}+1=v_i$ و $\delta_i = 0$ اگر $v_{i-1}+1\neq v_i.$ برای \(i=1\)، جمله‌ی آخر وجود ندارد.

رابطه‌ی بالا را از کوچک‌ترین قدرت به بزرگ‌ترین قدرت حساب کن. برای محاسبه‌ی \(s_i\)، لازم نیست همه‌ی \(s_i\)ها را جداگانه نگه داری. یک متغیر \(\mathrm{rem}\) نگه دار که ابتدا برابر \(n\) است. هنگام پردازش گروه \(i\)، داریم \[ s_i = \mathrm{rem}, \] و بعد از پردازش این گروه: \[ \mathrm{rem} \leftarrow \mathrm{rem} - c_i. \]

در پیمانه‌ی \[ M = 10^9+7 \] کسرها را با وارون پیمانه‌ای حساب کن: \[ \frac{a}{b} \equiv a \cdot b^{-1} \pmod M. \] چون همه‌ی مخرج‌ها بین \(1\) تا \(n\) هستند، همه‌ی وارون‌ها را می‌توان در زمان خطی پیش‌محاسبه کرد.

در پیاده‌سازی، برای هر گروه فقط این داده‌ها لازم است: \[ v_i,\quad c_i,\quad s_i,\quad p_{i-1},\quad v_{i-1}. \] پس بعد از مرتب‌سازی و گروه‌بندی، بقیه‌ی حل خطی است.

در پایان اگر \[ P = \sum_{i=1}^{m} p_i, \] آنگاه جواب نهایی برابر است با \[ n! \cdot P \pmod M. \] مراقب منفی شدن مقدارها بعد از تفریق باش و در صورت نیاز \(M\) اضافه کن.

پیچیدگی زمانی راه‌حل \[ O(n\log n) \] است، چون باید قدرت‌ها را مرتب کنیم. بعد از مرتب‌سازی، گروه‌بندی و محاسبه‌ی جواب در زمان \[ O(n) \] انجام می‌شود.