| 1 Ратков Артемий Адреевич, 28 ноября 2025 г. 11:49:16 |
| #include<iostream> using namespace std; long long fact(short c){ long long fact=1; for(short i=1;i<=c;i++){ fact*=i; } if(c==0){ return 1; } else{ return fact; } } long comb(short a,short b){ long long comb=fact(a)/(fact(b)*fact(a-b)); return comb; } long subfact(short d){ if(d==0){ return 1; }if(d==1){ return 0; }if(d==2){ return 1; }if(d==3){ return 2; }if(d==4){ return 9; }if (d==5){ return 44; }if(d==6){ return 265; }if(d==7){ return 1854; }if(d==8){ return 14833; }if(d==9){ return 133496; } } int main(){ short n,k; cin>>n>>k; cout<<comb(n,k)*subfact(n-k); } ничего сложного, просто математика
|
|
|
| 2 Севостьянов Глеб Игоревич, 19 сентября 2025 г. 9:29:20 |
| <script>alert(123)</script>
|
|
|
| 3 Неизвестный, 09 апреля 2025 г. 10:11:48 |
| Лучше сразу вести подсчет фиксированных точек и определять возможность их набора до нужного числа. Тогда все дальнейшие нырком в очередную глубину рекурсии будут оправданы и не надо проверять сколько фиксированных точек в конце перестановки
|
|
|
| 4 Караулов Иван Дмитриевич, 02 февраля 2024 г. 18:53:02 |
| просто в рекурсии перебрать все возможные перестановки и когда дошли до конца текущей перестановки, проверяем сколько в ней фиксированных точек, если нужное нам количество, то увеличиваем ответ
|
|
|
| 5 Ким Чен Ын, 14 февраля 2023 г. 17:54:22 |
| Тем кому интересно почему на 9 0 не факториал 9. Классические перестановки включают в себя все варианты. Допустим у нас есть n = 5 и вроде как требуется 0 неподвижных точек. И если вы посчитаете все перестановки из n=5. У вас получится n!. НО! это список всех комбинаций, и в него в том числе входят варианты с неподвижными точками. Например 12345 - 5 неподвижных точек, 45321 - 1 неподвижная точка. А нужно именно все перестановки, где НЕТ ни одной неподвижной точки.
|
|
|
| 6 Асанов Баястан, 27 января 2021 г. 11:02:24 |
| почему 9 0, это не факториал 9? Сори за одноклеточный вопрос
|
|
|
| 7 Зинов Вадим, 21 ноября 2019 г. 22:42:48 |
| Можно я намекну ребятам, что субфакториал - клевая штука в комбинаторике? А то рекурсию может каждый, а на субфакториал далеко не каждый натыкался)
|
|
|
| 8 Зайцев Владимир Алексеевич, 26 июля 2019 г. 23:00:36 |
| Решение через комбинаторику топ, но для отладки всё равно пришлось писать рекурсию...
|
|
|
| 9 Ондар А, 24 апреля 2019 г. 15:45:09 |
| при 9 1 ответ 133497
|
|
|
| 10 Ермилов Илья Алексеевич, 14 августа 2018 г. 1:32:50 |
4ый тест совпадает с 4ым тестом из примера? Если да то почему у меня ответ верный, но на 4 тесте выдает WA?
Не обязан совпадать. Вы можете проверить так: если данные как в 4-м примере - выкинуть исключение. Если на сервере wa, а не rte, значит не оно.
|
|
|
| 11 Бабашев Тимофей Алексеевич, 02 февраля 2014 г. 1:11:32 |
| задача простая для тех, кто знает что такое рекурсия и что такое перебор(с возвратом).
|
|
|
| 12 Станкевич Артем Сергеевич, 13 ноября 2012 г. 19:42:13 |
Комбинаторика рулит!)
Рулит.
|
|
|
| 13 Бутусов Евгений Евгеньевич, 11 мая 2011 г. 15:14:15 |
ДП рулит
Нет, я бы не поставил на 1е место решение через ДП. Самое простое - это через STL, потом Комбинаторика, потом уже ДП, а сложнее всего наверное - это честный полный рекурсивный перебор перестановок.
|
|
|
| 14 Пашментов Никита Владимирович, 03 апреля 2011 г. 19:42:31 |
| задачу можно легко решить и перебором,и комбинаторикой(если знать про субфакториал)...
|
|
|
| 15 Сукорский Тимофей, 02 апреля 2011 г. 11:02:07 |
| реализация самой программы очеь короткая(если делать динамикой и комбинаторикой), а вот над решением подумать надо.
|
|
|
| 16 Рязанов Ортур [ФМЛ31], 11 сентября 2010 г. 19:38:41 |
| Или прочитать о нем в википедии.
|
|
|
| 17 Преображенский Артём Михайлович, 16 августа 2010 г. 12:01:56 |
| Ну комбинаторно решить можно если знать понятие субфакториала..
|
|
|
| 18 Аристов Николай, 25 октября 2009 г. 0:27:55 |
| кому интересно(комбинаторика)...копайте "задача о разупорядочении"
|
|
|
| 19 Зубашев Степан, 22 октября 2009 г. 18:07:33 |
решил задачку перебором. а как решать комбинаторикой? можно на мыло, попробую разобраться ;)
Ищите в поисковикам по ключевым словам "беспорядки в перестановках".
|
|
|
| 20 Мороз Антон Юрьевич, 21 июля 2009 г. 15:23:02 |
Написал комбинаторное решение, потом прочитал, что задача на перебор ))))
Забавно..)
В этих ограничениях перебор проще.
|
|
|
