ABC 196/D - Hanjo

문제 개요

참조 소스: /atcoder.jp/contests/abc196/tasks/abc196_d

HxW의 송어로 구성된 접시 위에 1x2 덩어리 A장을 놓아라.2A\leqHW 보증주괴가 얼마나 됩니까?

해법

공식 설명서를 보면 DFS 테스트만이 모든 배치 방법을 보여줍니다.계산량을 가늠할 수 있기 때문에 알면 문제없지만 미리 계산량 상한선을 주는 해법을 준다.
송어마다 다음과 같은 세 가지 상태가 있다.

배치되지 않은 블록

블록 가로 배치

블록 세로 배치

이것을 감안하면 3^{HW} 그렇다.HW\leq16이라고 해서 3^{HW}\leq43046721입니다. 그런데 이 중에서 더 검증이 되면 TLE가 됩니다.
좀 더 자세하게 아래처럼 세분화

HW 송어 중 A 송어를 선택,

블록을 가로(오른쪽) 또는 세로(아래) 방향으로 배치

이렇게 생각하면...
\binom{HW}{A}\times 2^A\leq 3,294,720
를 참고하십시오.이렇게 되면 파리에서 O(HW)를 쳐도 상관없다.
2^A 거리의 전체 탐색은 비트집합의 생각에서 비교적 쉽게 실현할 수 있다.

for iset in range(1 << A):
  # iset の i-th bit が立ってるかどうかでどうこうする

다른 한편\binom{m}{n}거리의 전체 탐색도 단순하지는 않지만, 착실하게 실시하면 어렵지 않다.나는 자신의 도서관을 실행하고 경기에서 이것을 복제한다.

ans = 0
for p in binom(H * W, A):  # binom{mn}{a}
  for q in range(1 << A):
    # 実際に置いてみて, 重なることのないことをチェック
    if validate(p, q):
      ans += 1
print(ans)