코후닝

순열 교환 백준 다항식 · NTT 스털링 수 더블링 Java 문제 분석 순열 A가 주어졌을 때, 정확히 k번 교환해서 A를 만드는 서로 다른 순열 B의 개수 k = 1부터 n−1까지 모든 값에 대해 답을 구해야 함 제약: N ≤ 100,000 / 답은 mod 109+7 핵심 관찰: 답은 A에 무관하다! → “정확히 k개 전치의 곱으로 표현 가능한 순열의 수”와 동치 접근법 1. 수학적 환원 순열 σ의 사이클 수 = c일 때, 최소 전치 수 = n − c σ가 정확히 k개 전치의 곱 ⇔ n − c ≤ k and n − c ..