[Hard] TheCowDivOne

이런 타입의 조합문제는 조합의 수를 구하는 것보다 순열의 수를 구한 뒤 중복을 제거하는게 더 쉬울 수 있다. 문제를 다음과 같이 바꿔보자. F(d, k, a) = (X[1] + X[2] + ... + X[k-1] + a * X[k]) % d == 0 이고 0 <= X[i] < N 인 순열 X의 수. 그리고 d는 N의 약수여야 함. 이러면 원래 문제의 답은 F(N, K, 1) / K! 이 될 것이다. 문제를 이렇게 바꾸는 데에도 상당한 논리전개 과정이 있는데 이건 생략함. 에디토리얼에 잘 나와있음. S = X[1] + X[2] + ... + X[k-1] 이라 하면 위 식은 (S + a * X[k]) % d == 0 이 되고, 이걸 정리하면 a * X[k] % d = -S % d -S % d 의 값은 a*0 % d, a*1 % d, ... a*(N-1) % d 중의 하나인데, d는 N의 약수라고 했으므로 a*0 % d, a*1 % d, ..., a*(d-1) % d 가 N/d 번 반복될 것이다. 그리고 g = gcd(a, d) 라고 하면 모듈러의 성질에 의해 위의 값들은 g*0 % d, g*1 % d, ..., g*(d/g-1) % d 가 g번 반복되는 형태고 이 값들은 모두 다르다. 따라서 S가 특정 값으로 정해지면, 위의 등식을 만족하게 되는 X[k] 의 값은 (N/d) * g개가 된다. 게다가 S는 g의 배수여야 한다는 사실도 알 수 있다. S = X[1] + X[2] + ... + X[k-1] 이라 했는데, S는 g의 배수여야 한다고 했으므로 결국 (X[1] + X[2] + ... + X[k-1]) % g = 0 이다. 여기까지를 정리하면 F(d, k, a) = F(g, k-1, 1) * (N/d) * g 이다. 그런데 X[k] 로 고른 수가 X[1] ~ X[k-1] 에서 등장한 수였을 수 있다. 그 중복을 제거해야한다. X[1] ~ X[k-1] 까지는 순열이므로 만약 X[k]가 중복되었다면 그 수는 앞에서 정확히 한번 등장해야한다. 한번 등장한 중복된 수를 X[i] 라고 하면, 이 때 우리가 제거해야할 중복의 수는 결국 (X[1] + X[2] + ... + (a+1)*X[i] + ... + X[k-1]) % d = 0 인 순열의 수와 같을 것이다. 대칭에 의해 다른 i에 대해서도 모두 성립하고 따라서 최종적으로 제거해야할 중복의 수는 (k-1) * F(d, k-1, a+1) 가 되고, 결국 F(d, k, a) = F(g, k-1, 1) * (N/d) * g - (k-1) * F(d, k-1, a+1) 이다!!!!!!!!! 힘들었다... 점화식의 모양을 보면 맨처음에 걸었던 제약조건 "d는 N의 약수여야 함" 이 잘 지켜지는 것을 알 수 있다. 이걸 단순히 돌리면 TLE각이고, 한가지 최적화를 할 수 있는데 (X[1] + X[2] + ... + X[k-1] + a * X[k]) % d == 0 에서 a를 a%d 로 바꿔도 결과는 같다 따라서 F(d, k, a) = F(g, k-1, 1) * (N/d) * g - (k-1) * F(d, k-1, (a+1)%d) 로 쓸 수 있다.