Codeforces Round #355 (Div. 2) C 预处理
1 second
256 megabytes
standard input
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.
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
结果乘积并取模
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#define ll __int64
#define pi acos(-1.0)
#define mod 1000000007
using namespace std;
map<char,int> mp;
ll a[];
char b[];
ll quickmod(ll a,ll b)
{
ll sum=;
while(b)
{
if(b&)
sum=(sum*a%mod);
b>>=;
a=(a*a%mod);
}
return sum;
}
void init ()
{
for(int i=;i<=;i++)
{
int n=i;
int c=;
while (n >)
{
if((n &) ==)
++c ;
n >>= ;
}
a[i]=quickmod(,-c);
}
int jishu=;
for(int i='';i<='';i++)
{
mp[i]=a[jishu];
jishu++;
}
for(int i='A';i<='Z';i++)
{
mp[i]=a[jishu];
jishu++;
}
for(int i='a';i<='z';i++)
{
mp[i]=a[jishu];
jishu++;
}
mp['-']=a[];
mp['_']=a[];
}
int main()
{
init();
ll ans=;
scanf("%s",b);
int len=strlen(b);
for(int i=;i<len;i++)
ans=(ans%mod*mp[b[i]])%mod;
cout<<ans<<endl;
return ;
}
最新文章
- Java基础知识笔记(六:网络程序设计)
- C#将字节流加密解密
- silverlighter下MVVM模式中利用Behavior和TargetedTriggerAction实现文本框的一些特效
- Problem 2136 取糖果---FUOJ (线段树+维护)
- override 与 overdown 的区别
- 修改tabbarcontroller选中图片及选中颜色
- AndroidPN中的心跳检测
- c语言位运算符
- Myeclipse自动生成javabean的get和set方法
- 一.oracle的SQL中group by使用的情况(与聚合函数的关系)
- IE的事件与w3c事件的区别
- SpringData系列三 Repository Bean 方法定义规范
- 在Apworks数据服务中使用基于Entity Framework Core的仓储(Repository)实现
- IOS学习【前言】
- IMLite轻量级即时通信工具开发指南
- 201621123060《JAVA程序设计》第十三周学习总结
- DSAPI 网页获取本地程序登陆用户
- leetcode — reverse-linked-list
- Get started with Docker for Windows
- 【转】Unity3D的LightProbe动态光探头用法介绍
热门文章
- js动画之无缝滚动
- js字符转数字
- axios进行ajax请求得不到数据,cookie无法携带问题
- tcl之过程/函数-proc
- PHP CI框架学习
- SpringMVC---applicationContext.xml配置详解
- SLB 7层负载均衡“HUNG”问题追查
- oracle数据库DB_NAME、DBID、DB_UNIQUE_NAME等的区别
- 《Cracking the Coding Interview》——第17章:普通题——题目14
- leetcode 【 Remove Duplicates from Sorted List II 】 python 实现