On Wednesday I have participated in a codeforces.com competition and it was not as quite successful as I wished it to be. I managed to solve 2 problems and 1 of them was “hacked”, which means 1 problem. Anyhow, I was tired (it was on Wednesday right after work) and the weather was bad and etc. 🙂
Today I recalled seeing the third problem in the competition and being not able to grasp what actually should be done there for about 10 minutes. When I finally get it, I was probably too tired to think of a solution, thus I have left it for the weekend 🙂
Today I have started to think about a solution once again and I finally found one that works 🙂 The problem is challenging and interesting as far as I have not worked with bit operators for a long time.
The problem is available here. This is how it looks like:
While walking down the street Vanya saw a label “Hide&Seek”. Because he is a programmer, he used & as a bitwise AND for these two words represented as a integers in base 64 and got new word. Now Vanya thinks of some string s and wants to know the number of pairs of words of length |s| (length of s), such that their bitwise AND is equal to s. As this number can be large, output it modulo 109 + 7.
To represent the string as a number in numeral system with base 64 Vanya uses the following rules:
- digits from ‘0‘ to ‘9‘ correspond to integers from 0 to 9;
- letters from ‘A‘ to ‘Z‘ correspond to integers from 10 to 35;
- letters from ‘a‘ to ‘z‘ correspond to integers from 36 to 61;
- letter ‘–‘ correspond to integer 62;
- letter ‘_‘ correspond to integer 63.
The only line of the input contains a single word s (1 ≤ |s| ≤ 100 000), consisting of digits, lowercase and uppercase English letters, characters ‘–‘ and ‘_‘.
Print a single integer — the number of possible pairs of words, such that their bitwise AND is equal to string s modulo 109 + 7.
Honestly, if you understood from the first reading what is required by you I am quite happy to have you reading my blog! I myself could not… Today, few days later I read it a couple more times and finally something came in my mind about what is needed to be done.
First things first – we obviously have some string as input, in which every char is translated into a number from 0 to 63. Quite convenient, because that is “11111” binary:
Once we get the value of the char, we should ask ourself the tricky question – how many options do we have, in order to have bitwise AND for this value equaling 0. The idea with the 0 is that if we have a zero as an input, we have the following three options to have bitwise AND – ((0 and 0)(0 and 1)(1 and 0)). If we have a 1, the only way to have equal AND is to have 1 as well. Thus, we do not need to consider the 1. Thus, once we count all the possible zeroes per string, with binary comparing we get an answer. This answer should be multiplied by 3, because of the possible variations. In order to make our solution working, we use result %= mod in the loop, as far as the number is going pretty big.
Pretty much that is all. Probably you would need about 20 minutes to find out what is happening in the code, but I needed much more to write it down!
Here is comes:
|
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 |
using System; class vitbit { static void Main() { string input = Console.ReadLine(); long zeroes = 0; foreach (char my_char in input) { long i = GenerateValue(my_char); for (int j = 5; j >= 0; j--) { if (((i >> j) & 1) == 0) zeroes++; } } long result = 1; long mod = (long)(Math.Pow(10, 9))+7; for (long i = 0; i < zeroes; i++) { result *= 3; result %= mod; } Console.WriteLine(result); } static long GenerateValue(char my_char) { if (my_char >= '0' && my_char <= '9') return my_char-'0'; if (my_char >= 'a' && my_char <= 'z') return my_char - 'a' + 36; if (my_char >= 'A' && my_char <= 'Z') return my_char - 'A' + 10; if (my_char == '-') return 62; return 63; } } |