| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 512 MB | 117 | 76 | 69 | 72.632% |
In geometry, ellipses are defined by two focal points f1, f2 and a length D. The ellipse consists of all points p such that distance(f1, p) + distance(f2, p) = D.
When one normally thinks of ellipses, it is in the context of the Euclidean 2D plane, with the Euclidean distance as a distance measure.
This problem explores a different kind of ellipse. The space we will work in is the space of words of length n using an alphabet of q different symbols, often denoted as Fnq. As you can probably see, for given values of q and n, there are qn different words (points) in the space Fnq.
For a distance measure, we use the Hamming distance. The Hamming distance between two words x, y ∈ Fnq is simply the number of positions where the symbols that make up the words x and y differ. For example, the Hamming distance between words 01201 and 21210 is 3 because there are 3 positions where the words have different symbols. The Hamming distance between any two words in Fnq will always be an integer between 0 and n, inclusive.
Within the space Fnq, we now define the Hamming ellipse as the set of all points p such that hammingdistance(f1, p) + hammingdistance(f2, p) = D. Given values q and n, focal points f1 and f2 and distance D, we ask you to determine the number of points p ∈ Fnq that lie on this Hamming ellipse.
The first line contains three integers q (2 ≤ q ≤ 10), n (1 ≤ n ≤ 100) and D (1 ≤ D ≤ 2n).
The second and third lines specify the two focal points f1 and f2, each formatted as a string of length n using digits {0, 1 . . . q − 1}
Output one line containing a single integer, denoting the number of points on the ellipse. The input is chosen such that the answer is less than 263.
3 5 9 01201 21210
24
4 6 5 123031 231222
0
2 32 32 01010101010101010101010101010101 01010101010101010101010101010101
601080390