[Hard] GameOfLifeDivOne

게임판이 원형이므로 한 지점을 잘라서 일자로 편 후에 그 게임판을 뒤에 한번 더 붙이면 원형을 흉내낼 수 있다. 그렇게 만든 일자 게임판에서 생각하기로 하자. 게임의 진행과정을 잘 살펴보면 몇가지 특징을 발견할 수 있다. 우선 0이 2개 이상, 혹은 1이 2개 이상 모여있으면 그것들은 영원히 변하지 않는다. 따라서 게임판은 0혹은1의 연속된 '블럭'과 '블럭이 아닌 부분'들로 나뉘어지게 되고 '블럭'은 우리의 관심에서 제외해도 된다. '블럭이 아닌 부분'을 어떻게 배치할지만 관심을 가지면 된다. ...00000[010101]1111[101]111[1010][01010]000[010101]111... (블럭이 아닌 부분의 예) '블럭이 아닌 부분'은 시간에 따라 어떻게 변해가는지 살펴보자. 00블럭으로 둘러싸인 구간의 길이가 2*k+1 인 경우는 다음과 같다. 예를 들어 001010100 이 있으면 이 패턴은 001010100 -> 000101000 -> 000010000 -> 000000000 으로 변해간다. 즉, T초 후에 내부의 1의 개수는 max(k + 1 - T, 0) 이 된다. 11블럭으로 둘러싸인 구간의 길이가 2*k+1 인 경우는 다음과 같다. 예를 들어 110101011 이 있으면 이 패턴은 110101011 -> 111010111 -> 111101111 -> 111111111 로 변해간다. 즉, T초 후에 내부의 1의 개수는 min(k + T, 2 * k + 1) 이 된다. 서로 다른 블럭으로 둘러싸인 구간의 길이가 2*k 인 경우는 다음과 같다. 예를 들어 00101011 이 있으면 이 패턴은 00101011 -> 00010111 -> 00001111 로 변해간다. 즉, T초 후에 내부의 1의 개수는 변함이 없다. 위에서 정리한 성질을 이용해 우선 다음과 같은 함수를 만들 수 있다. oneCntInBlock[i][x][j][y] = i j ..xxxabababab...yyy.. '?'에 적당히 assign을 해서 문자열 패턴이 다음과 같이 되었을 때, 즉, str[i..j-1] 를 '블럭이 아닌 부분'으로 만들었고 왼쪽에는 x블럭, 오른쪽에는 y블럭이 둘러싸고 있을 때 T초 후에 str[i..j-1] 에 존재하는 1의 개수 이 함수는 위의 성질을 이용해 쉽게 계산할 수 있다. 그 다음은, 이 함수를 이용해 '블럭이 아닌 부분'을 앞에서부터 잘 쌓아가면 된다. 이건 DP로 해결할 수 있다. 쌓아가는 시작점을 stpos, 그 지점의 bit를 stb 라고 하자. (stpos, stb) 의 모든 쌍을 돌면서 다음과 같은 DP를 돌린다. D[i][ib][one] = str[stpos..i-1] 의 '?'을 적절히 채워서 T초후에 이 부분에 1이 one개 있는 경우의 수 거기에 더해 str[i] = ib 로 세팅함 D[stpos][stb][0] = 1 i < j 이고, 유효한 값이 있는 oneCntInBlock[i][ib][j][jb] 에 대해 D[j][jb][one + oneCntInBlock[i][ib][j][jb]] += D[i][ib][one] 으로 갱신해주면 된다. 답은 sum( D[n + stpos][stb][one] , K <= one <= n ) 답을 중복해서 세지 않기 위해 기준을 잘 잡아야 한다. 그러기 위해서 stpos는 str[stpos] == str[stpos-1] 가 되는 제일 작은 index 여야 한다. 따라서 dp를 갱신할 때 j == n + stpos 라면, i < n 일 때만 갱신해줘야 한다. str[n..j-1] 사이에는 연속된 블럭이 나타나지 않도록 상황을 제한하는 것이다. 여기에 더해 단 하나의 예외가 있는데 게임판 전체가 0101010101.... 처럼 되어있어 '블럭' 이 하나도 등장하지 않는 상황을 고려해야한다. K <= n/2 면서 oneCntInBlock[0][0][n][1] 이나 oneCntInBlock[0][1][n][0] 에 유효한 값이 들어있으면 바로 그런 경우이다.