PIN (CEOI 2010)

http://main.edu.pl/en/archive/ceoi/2010/pin

편의상 입력되는 문자열을 [0, 35] 사이의 정수 4개라고 생각하자.

D[A][B][C][D] 을 (0 <= A, B, C, D <= 36)

 * A < 36일시 1번째 수 == A, 아닐시 1번째 수가 뭐든 true

 * B < 36일시 2번째 수 == B, 아닐시 2번째 수가 뭐든 true

 * C < 36일시 3번째 수 == C, 아닐시 3번째 수가 뭐든 true

 * D < 36일시 4번째 수 == D, 아닐시 4번째 수가 뭐든 true

.. 를 만족하는 입력의 경우의 수라고 하자.

D[A][B][C][D] 를 구했을 경우, 이제 다음과 같은 T[] 배열을 채우자.

 * T[K] = 와일드카드(36)가 K (1 <= K <= 4) 개 채워진 D[][][][] 값 T에 대해서, TC2의 합.

정확히 K개 다른 경우의 수를 R[K] 라고 할 때, 다음과 같은 식이 성립한다.

 * T[1] = R[1]

 * T[2] = R[2] + R[1] * 3

 * T[3] = R[3] + R[2] * 2 + R[1] * 3

이해가 안 가면, 그러한 쌍이 저 T[] 배열의 값에 얼마나 "기여" 하는지를 고민해보면 좋을 것이다. 방정식을 풀면

 * R[1] = T[1]

 * R[2] = T[2] - T[1] * 3

 * R[3] = T[3] - 2 * (T[2] - 3 * T[1]) - 3 * T[1]

또한, R[4] = nC2 - R[3] - R[2] - R[1]이다. 고로 답을 구할 수 있다.