문제풀이
- 비트 마스킹을 통해 개수를 저장한다.
- prev[i] = 현재 인덱스까지 만들 수 있는 부분 문자열에서 등장하는 i의 개수
주의사항
소요시간
18분
package AtCoder.ProblemList.Difficulty800_1199.ThreeDaysAgo
fun main() {
val S = readln().trim()
val prev = LongArray(1 shl 10)
val next = LongArray(1 shl 10)
var result = 0L
for (s in S) {
for (i in prev.indices) {
next[i xor (1 shl (s - '0'))] += prev[i]
}
for (i in prev.indices) {
prev[i] = next[i]
next[i] = 0
}
prev[1 shl (s - '0')]++
result += prev[0]
}
println(result)
}