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.
z
3
V_V
9
Codeforces
130653412
For a detailed definition of bitwise AND we recommend to take a look in the corresponding article in Wikipedia.
In the first sample, there are 3 possible solutions:
- z&_ = 61&63 = 61 = z
- _&z = 63&61 = 61 = z
- z&z = 61&61 = 61 = z
题意:不同字符表示0~63 给你一个字符串判断 有多少对 长度相同的字符串的 &运算的结果 为所给的字符串
题解:模拟
1&1=1 0&1=0 1&0=0 0&0=0
打表预处理 0~63的满足情况的对数
例如31=(11111)2
共有三对 111111&011111
011111&111111
011111&011111
结果乘积并取模
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<queue> 5 #include<stack> 6 #include<cmath> 7 #include<map> 8 #define ll __int64 9 #define pi acos(-1.0) 10 #define mod 1000000007 11 using namespace std; 12 map<char,int> mp; 13 ll a[100]; 14 char b[100005]; 15 ll quickmod(ll a,ll b) 16 { 17 ll sum=1; 18 while(b) 19 { 20 if(b&1) 21 sum=(sum*a%mod); 22 b>>=1; 23 a=(a*a%mod); 24 } 25 return sum; 26 } 27 void init () 28 { 29 for(int i=0;i<=63;i++) 30 { 31 int n=i; 32 int c=0; 33 while (n >0) 34 { 35 if((n &1) ==1) 36 ++c ; 37 n >>=1 ; 38 } 39 a[i]=quickmod(3,6-c); 40 } 41 int jishu=0; 42 for(int i='0';i<='9';i++) 43 { 44 mp[i]=a[jishu]; 45 jishu++; 46 } 47 for(int i='A';i<='Z';i++) 48 { 49 mp[i]=a[jishu]; 50 jishu++; 51 } 52 for(int i='a';i<='z';i++) 53 { 54 mp[i]=a[jishu]; 55 jishu++; 56 } 57 mp['-']=a[62]; 58 mp['_']=a[63]; 59 } 60 int main() 61 { 62 init(); 63 ll ans=1; 64 scanf("%s",b); 65 int len=strlen(b); 66 for(int i=0;i<len;i++) 67 ans=(ans%mod*mp[b[i]])%mod; 68 cout<<ans<<endl; 69 return 0; 70 }