codeforces 677C C. Vanya and Label(组合数学+快速幂)

题目链接:

C. Vanya and Label

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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.
 
Input
 

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 '_'.

 
Output
 

Print a single integer — the number of possible pairs of words, such that their bitwise AND is equal to string s modulo 109 + 7.

 
Examples
 
input
z
output
3
input
V_V
output
9
input
Codeforces
output
130653412

题意:

每一位用这些字符来代替,问有多少对与s相同长度的字符串的&运算之后等于s;

思路:

把这些字符转化成数字后变成2进制,看有多少个0,如果有n个0,那么就是3的n次方;
因为每一个为0的位置上可以有0&1,1&0,0&0,这3种情况,最后结果就是3的n次方了,快速幂; AC代码:
#include <bits/stdc++.h>
/*#include <vector>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <cstring>
#include <algorithm>
#include <cstdio>
*/
using namespace std;
#define Riep(n) for(int i=1;i<=n;i++)
#define Riop(n) for(int i=0;i<n;i++)
#define Rjep(n) for(int j=1;j<=n;j++)
#define Rjop(n) for(int j=0;j<n;j++)
#define mst(ss,b) memset(ss,b,sizeof(ss));
typedef long long LL;
template<class T> void read(T&num) {
char CH; bool F=false;
for(CH=getchar();CH<''||CH>'';F= CH=='-',CH=getchar());
for(num=;CH>=''&&CH<='';num=num*+CH-'',CH=getchar());
F && (num=-num);
}
int stk[], tp;
template<class T> inline void print(T p) {
if(!p) { puts(""); return; }
while(p) stk[++ tp] = p%, p/=;
while(tp) putchar(stk[tp--] + '');
putchar('\n');
} const LL mod=1e9+;
const double PI=acos(-1.0);
const LL inf=1e10;
const int N=1e5+;
char s[N];
int check(int x)
{
if(s[x]>=''&&s[x]<='')return s[x]-'';
else if(s[x]>='a'&&s[x]<='z')return s[x]-'a'+;
else if(s[x]>='A'&&s[x]<='Z')return s[x]-'A'+;
else if(s[x]=='-')return ;
else if(s[x]=='_')return ;
}
int fun(int x)
{
int num=;
int cnt=;
while(cnt--)
{
if(x%==)num++;
x=(x>>);
}
return num;
}
LL fastpow(int y)
{
LL ans=,base=;
while(y)
{
if(y&)
{
ans=ans*base;
ans%=mod;
}
base=base*base;
base%=mod;
y=(y>>);
}
return ans;
} int main()
{
scanf("%s",s);
int len=strlen(s);
int sum=;
for(int i=;i<len;i++)
{
int x=check(i);
sum=sum+fun(x);
}
print(fastpow(sum));
return ;
}


上一篇:React Native之配置开发环境


下一篇:史上最详细Windows版本搭建安装React Native环境配置 转载,比官网的靠谱亲测可用