I'm solving a problem in which I need to store the frequency of each digit from 0 to 9 in a bitmask.
Is it possible to do this?
If yes, then how?
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 17.11.2024 22:30:35 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
ignore
But it only stores the parity of frequency. It doesn't store numerical frequency. Actually the question is a digit dp question in which I have to count all numbers in a range which have Freq of each digit as K, where K is given. So I was thinking how to make a dp state store the frequency.
problem link please
Bitmask stores 0/1 values so it would work only to check if the frequency is 0 or more.
You can represent every frequency as a binary number, e.g. 5 = 101, and write them one by one. It will be annoying. In particular, you need to figure out what's the length of every number. If each frequency is up to 100, you need 7 bits per number because $$$100 \leq 2^7$$$. The bitmask needs a length $$$70$$$ then.
If highest frequency is F Then you can represent the number in a number system base F So, dp will look like dp[F][F][F][F][F][F][F][F][F][F]. You can compress it in dp[F^10]