1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <utility>
#include <vector>

#define REP(a, n) for (int a = 0; a < (n); ++a)
#define FOR(a, b, c) for (int a = (b); a <= (c); ++a)
#define FORD(a, b, c) for (int a = (b); a >= (c); --a)

typedef long long LL;

using namespace std;

template<class T> inline int vsize(const T &t) { return t.size(); }

/////////////////

int stos[32], wys, ile_st, ile_st_max;
LL wyn[33], potegi_w1[34] = {1};
vector<bool> przegr[2];
vector<bool> byl[2];

bool licz(int gracz, LL konf) {
    if (byl[gracz][konf])
        return przegr[gracz][konf];
    byl[gracz][konf] = 1;
    REP(s, ile_st) {
        int ww = konf/potegi_w1[s]%(wys+1);
        REP(w, ww)
            if ((gracz==0 && !(stos[s]&(1<<w))) || (gracz==1 && (stos[s]&(1<<w)))) {
                LL k2 =  konf/potegi_w1[s+1]*potegi_w1[s+1] + w*potegi_w1[s] + konf%potegi_w1[s];
                if (licz(!gracz, k2))
                    return przegr[gracz][konf] = 0;
            }
    }
    return przegr[gracz][konf] = 1;
}

void symuluj() {
    REP(a, 2) {
        przegr[a].resize(potegi_w1[ile_st]);
        byl[a].clear();
        byl[a].resize(potegi_w1[ile_st]);
        byl[a][0] = 1;
        przegr[a][0] = 1;
    }
    bool x = licz(0, potegi_w1[ile_st]-1);
    bool y = licz(1, potegi_w1[ile_st]-1);
    if (x && y) {
        wyn[ile_st]++;
//        fprintf(stderr, "%d %d %d (%d)\n", stos[0], stos[1], stos[2], ile_st);
        }
}

void probuj() {
    symuluj();
    if (ile_st < ile_st_max) {
        ++ile_st;
        for (stos[ile_st-1] = 0; stos[ile_st-1]<(1<<wys); stos[ile_st-1]++)
            probuj();
        --ile_st;
    }
}

int main() {
    scanf("%d%d%d", &ile_st_max, &wys, &ile_st);
    REP(a, ile_st) {
        char st[50];
        scanf("%s", st);
        REP(b, wys)
            if (st[b]=='C')
                stos[a] |= (1<<b);
        
    }
    FOR(a, 1, ile_st_max) potegi_w1[a] = potegi_w1[a-1]*(wys+1);
    potegi_w1[0] = 1;
    probuj();
    FOR(a, ile_st, ile_st_max)
        printf("%lld%c", wyn[a], a==ile_st_max ? '\n' : ' ');
}