Topcoder SRM 514 Div1(Medium) MagicalGirlLevelTwoDivOne

문제 링크

격자의 사이즈 N,M 이 주어진다. 각 판은 '.' 또는 '1'~'9' 의 숫자이다. 

그리고 n,m 이 주어지는데 n,m이란 어떠한 격자칸에서부터 시작하는 연속된 칸에 있는 수들의 합이 홀수가

되어야 한다는 제약 조건에 대한 변수이다. 칸에서 아래로 n칸의 합은 홀수여야하고,

오른쪽으로 m칸의 합도 홀수여야한다는 것이다. 물론 열 인덱스가 M-m+1 인 칸 까지만 적용되며

행 인덱스가 N-n+1 인 칸까지만 적용된다.

이 때 '.' 인 칸에 적절한 '1'~'9'의 수를 넣어주어 위에서 말한 조건을 만족하도록 하는 방법의 수를 구하는 문제이다.

일단 각 수가 홀수인지 짝수인지만 중요하기 때문에 현재 적혀있는 수가 실제로 몇이던 상관없고 짝수인지 홀수인지만

중요하기 때문에 먼저 짝수는 0, 홀수는 1이라고 바꿔생각해도 답은 같다. 그리고 우리가 정해주는 빈칸에도

홀수를 넣기로 결정했으면 '1','3','5','7','9' 중아무거나 하나만 넣으면 되므로 1을 넣었을 때만 계산해서

5를 곱해주면 되며, 짝수일 때는 '2','4','6','8' 4가지 이므로 0을 넣었다고 가정했을 때의 값에 4를 곱해준다.

그럼 열을 기준으로 설명하겠다. 어떤 칸에서부터 m칸을 더한값이 홀수가 되었다고 가정해보자.

이 때 연속된 m칸이 오른쪽으로 한칸 이동하는 경우를 생각해 보자. 만약 이전에 맨왼쪽칸이 홀수였다면

맨왼쪽칸을 빼면 짝수가 되므로 새로 추가되는 맨오른쪽칸은 홀수가 되어야한다. 반대로 맨왼쪽칸이 짝수였다면

이걸 빼면 그대로 홀수이므로 새로추가되는 맨오른쪽칸은 짝수가 되어야한다. 즉, 열 번호가 m만큼 차이나는

칸들은 무조건 홀,짝이 같아야 한다는 것을 알 수가 있다.

행에 대해서도 열과 마찬가지 이므로 앞으로 행은 생략하고 설명하겠다.

그럼 우선 주어진 입력에서 열번호를 m으로 나눈 나머지가 같은 칸인데 홀,짝이 다르게 주어진것이있으면

답은 무조건 0이라는 것을 알 수가 있다. 이 것을 먼저 예외 처리해준다면 열번호 % m이 같은 칸들은

홀,짝이 정해져있거나 정해져있지 않거나 둘중하나이다. 열번호 % m 이 같은 모든 칸들이 '.'일 때가 바로

홀,짝이 정해져 있지 않을 때이고, 하나라도 '.'이 아니라면 홀짝이 정해져있을 것이다.

그럼 일단 '.'이 아닌 칸은 우리가 새로 값을 적어넣을 수가 없기 때문에 열번호 % m 가 같은 칸들에 대해

홀짝을 정해주었다면 그 칸들중 '.'인 칸들의 개수만큼 4또는 5의 거듭제곱을 곱해주어야 한다. 왜냐하면

홀수로 정해주었다면 '.'인 모든 칸들에 각각 5가지의 숫자를 넣을 수가 있기 때문에 \(5^{'.'인칸의수}\)

를 답에 곱해주면 되는것이다. 그럼 이제 어떤 특정 칸의 홀짝이 정해지고나면 어떤식으로 계산해야 할지를

알게되었다. 그렇다면 홀짝을 어떻게 정해줄까? 

일단 열번호 % m 가 같은 칸들은 어차피 한칸이 정해지면 모두 똑같이 맞추어야 하기 때문에 이 칸들 중

딱 하나만 정해주면 되기 때문에 열 번호가 0~m-1 인 칸들에 대해서만 고려하며 행에 대해서도 마찬가지이므로

n x m 의 격자에 대해서만 검사를 하면된다. 그렇다고 쳐도 n과 m은 각각 10이 최대이므로 홀짝을 정해주어야

할 칸의 수는 최대 100개인데 100개에 대해 홀이냐 짝이냐를 정하려면 2^100가지의 경우의 수를 다 봐줘야

한다는 말이된다. 그런데 물론 이렇게 naive 하게하면 시간이 오래걸리기 때문에 더 빠르게 하는 방법이 있다.

조금만 생각해 보면 특정 행의 m개의 값의 합이 이미 홀수라면 그 다음 행부터는 정해줄 필요도 없다. 어차피

이미 조건을 만족하지 못하기 때문이다. 게다가 특정 행까지 봐주었을 때 현재 각각의 열에 존재하는 수들의 합의

홀짝이 있을 텐데 이값이 각각의 열마다 완전히 동일하면서 다음번에 봐주어야할 행의 번호가 같다면

뒤는 안봐도 경우의 수가 똑같기 때문에 앞에서 계산했다면 굳이 또 계산할 필요가 없다는 점을 이용하여

메모이제이션을 해보자. 현재 홀짝을 정해주어야하는 행번호와 이전 행까지 정해줌으로인해 만들어진 각 열의 원소들의

합의 홀짝상태, 이 두가지로 메모이제이션을 하면되고 행번호는 최대 10이며, 각열의 원소들의 합의 홀짝상태는

2^10 가지가 가능하다. 왜냐하면 홀이거나 짝이거나 둘중하나라는건 한비트(0또는1)로 표현이 가능하기 때문이다.

그럼 부분문제의 수는 10*2^10 이며, 각 부분문제를 계산하는데에 걸리는 시간은

현재 행의 홀짝관계를 정해주는데에 있어서 최대 2^10 가지의 경우에 대해 봐줘야하며, 행의 홀짝을 정했을 때에

각 열의 칸이 홀또는 짝이 됨으로서 수를 채워넣는 가짓수를 계산해야하므로 최대 10번을 돌려주어야하므로

부분문제당 10*2^10 번을 돌아야한다. 그럼 시간복잡도는 \(O(n\cdot{m}\cdot{2^{m+n}})\) 가 나올 것이다.

그리고 각각의 부분문제를 계산할 때 유의할점들은 뭐냐면

하나의 행의 m칸에 대해 2^m개의 비트마스크에 대해 순회를 할텐데

이미 홀짝이 정해져있는 칸과 내가 지금 정하려는 홀짝이 다르다면 안되므로 이 케이스는 넘어가며

같으면 새로 수를 써넣을 수 없으므로 넘어가진않되 답에 따로 계산하진 않는다.

그리고 각 칸에 대해 인덱스의 행번호%n, 열번호%m 가 현재 행,열 번호와 같은 칸들 중에 '.'인 칸의 수만큼

4나 5의 거듭제곱을 곱해주고 누적해주는 식으로 하면됨

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
class MagicalGirlLevelTwoDivOne {
public:
    int theCount(vector<string> palette, int n, int m);
};
 
int N,M;
ll dp[13][1<<10];
int pane[53][53];
int correct[13][13];
int cnts[13][13];
ll pow4[2503], pow5[2503];
ll go(int row, int state){
    if(row == N) return state == ((1<<M)-1);
    ll& cache = dp[row][state];
    if(cache != -1) return cache;
    cache = 0;
    for(int i = 0 ; i < (1<<M); i++){
        int cnt= 0;
        for(int j = i; j ; j>>=1) cnt+=(j&1);
        if(cnt%2==0) continue;
        bool ok = true;
        ll mult = 1;
        for(int j = 0 ; j < M; j++){
            if(correct[row][j] != -1 && correct[row][j] != ((i&(1<<j))>>j)) {ok = false; break;}
            mult = (mult * (((i&(1<<j))>>j)?pow5[cnts[row][j]]:pow4[cnts[row][j]])) % MOD;
        }
        if(ok) cache = (cache + (mult * go(row+1, state^i)) % MOD) % MOD;
    }
    return cache;
}
int MagicalGirlLevelTwoDivOne::theCount(vector<string> palette, int n, int m) {
    pow4[0] = pow5[0] = 1;
    for(int i = 1 ; i < 2503; i++)
        pow4[i] = (pow4[i-1] * 4) % MOD, pow5[i] = (pow5[i-1] * 5) % MOD;
 
    memset(dp,-1,sizeof(dp));
    memset(correct,-1,sizeof(correct));
    memset(pane,-1,sizeof(pane));
    memset(cnts,0,sizeof(cnts));
    N = n, M = m;
    int nn = palette.size();
    int mm = palette[0].size();
    for(int i = 0 ; i < nn; i++) 
        for(int j = 0 ; j < mm; j++)
            {if(palette[i][j]=='.') continue; pane[i][j] = (palette[i][j]-'0')%2;}
 
    for(int i = 0 ; i < nn; i++){
        for(int j = 0 ; j < mm; j++){
            if(pane[i][j] == -1) {cnts[i%N][j%M]++; continue;}
            if(correct[i%N][j%M] == -1) {correct[i%N][j%M] = pane[i][j]; continue;}
            if(correct[i%N][j%M] != pane[i][j]) return 0;
        }
    }
    return (int)go(0, 0);
}