| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (하단 참고) | 512 MB | 30 | 16 | 14 | 51.852% |
Alice와 Bob은 함께 과일 케이크를 만들었다. 케이크는 $R \times C$ 크기의 직사각형 모양이고, 각 1ドル \times 1$ 크기의 칸에는 딸기(S), 블루베리(B), 라즈베리(R) 중 딱 한 종류의 과일이 토핑으로 올라가 있거나 혹은 크림(.)만 발라져 있다.
아래 그림은 크기가 2ドル \times 2$인 케이크이다.
S) 있고, 우측 상단 $(1, 2)$에는 과일은 없고 크림만(.) 있다.B) 있고 우측 하단 $(2, 2)$에는 라즈베리가(R) 있다.Bob은 케이크를 총 $N-1$번 가로나 세로로 잘라서 총 $N$조각의 직사각형 모양의 크기가 더 작은 케이크를 만들어 친구들에게 나눠주고 싶다. 단, Bob이 케이크를 자를 때에는 아래 규칙에 따라 케이크를 $N-1$번 잘라야 한다.
Alice는 $N$명의 친구들이 좋아하는 과일이 무엇인지 알기 때문에, 각 친구가 받게 될 케이크에는 그 친구가 좋아하는 과일이 반드시 1ドル$개 이상 있도록 하고 싶다. 단, 위에 언급한 대로 케이크를 잘라 얻어진 조각은 반드시 1ドル$번 친구부터 $N$번 친구까지 순서대로 주어야 한다.
예를 들어 $N = 3$이고, 세 친구가 좋아하는 과일이 순서대로 딸기(S), 블루베리(B), 그리고 라즈베리(R)라 하자. 이때, 위의 2ドル \times 2$ 케이크를 3ドル$조각으로 자르기 위해 Bob은 총 2ドル$번 케이크를 잘라야 하고, 위 규칙을 따르면 아래와 같이 두 가지 방법이 있다.
1번째 자르기: 가로로 자르기
규칙대로 1ドル$번 친구에게 상단의 1ドル \times 2$ 케이크 조각을 준다. 이 조각은 딸기를 하나 포함한다.
하단의 1ドル \times 2$ 케이크를 2ドル,ドル 3ドル$번 친구에게 준다.
2번째 자르기: 세로로 자르기
1ドル \times 2$ 케이크를 세로로 잘라 좌측의 블루베리(B) 조각은 2ドル$번 친구에게 주고, 우측의 라즈베리(R) 조각은 3ドル$번 친구에게 준다.
1번째 자르기: 세로로 자르기
규칙대로 1ドル$번 친구에게 좌측의 2ドル \times 1$ 케이크 조각을 준다. 이 조각은 딸기 하나와 블루베리 하나를 포함한다.
우측의 2ドル \times 1$ 케이크를 2ドル,ドル 3ドル$번 친구에게 준다.
2번째 자르기: 가로로 자르기
2ドル \times 1$ 케이크를 가로로 잘라 상단의 크림(.) 조각은 2ドル$번 친구에게 주고, 하단의 라즈베리(R) 조각은 3ドル$번 친구에게 준다.
위의 두 가지 방법 중 세 친구 모두가 자신의 좋아하는 과일을 포함한 조각을 얻는 방법은 첫 번째 방법뿐이다.
입력으로 케이크의 크기 및 과일이 올려진 형태, 그리고 친구들이 좋아하는 과일이 주어졌을 때, 몇 가지 다른 방법으로 케이크를 자를 수 있는지 구해보자.
입력 첫 줄에는 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $R,ドル $C,ドル $N$이 공백으로 구분되어 주어진다. 다음 $R$줄에 걸쳐 각 줄에 길이가 $C$인 문자열이 주어지는데, 이는 케이크의 토핑 과일이 무엇인지 (혹은 크림만 있는지) 알려준다. $R+2$번째 줄에는 길이 $N$인 문자열이 주어지는데, 이는 $N$명의 친구가 좋아하는 과일의 종류이다.
본문에 기술된 규칙에 따라 Bob이 $N-1$번 케이크를 자를 때 $N$명의 친구가 모두 만족할 수 있도록 (즉, 각 친구가 원하는 과일이 케이크 조각에 최소 1ドル$개 이상 포함되도록) 자르는 방법의 수를 구해 출력한다. 단, 이 값이 매우 클 수 있으므로 10ドル^9+7$로 나눈 나머지를 출력한다.
S', 'B', 'R', '.' 네 개중 하나이다.S', 'B', 'R' 세 개중 하나이다.6 2 2 3 S. BR SBR 2 2 3 S. BR SRB 1 6 3 SBRSBR SBR 3 4 4 S... .SR. ...B SSRB 3 3 2 SBS BSB SBS SB 1 50 10 SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS SSSSSSSSSS
1 0 7 4 4 54455620
예제 1: 본문에서 다루었다.
예제 2: 예제 1과 같은 케이크이지만, 세 명의 친구가 원하는 과일의 종류가 다르다.
예제 6: 가짓수가 매우 커질 수 있으므로 10ドル^9+7$로 나눈 나머지를 출력해야함에 유의하자.