HackerRank 101 Hack July'14 3問目
problem statement(コンテストページ)
problem statement
C言語にならって,ビットワイズ排他的論理和 $x\ {\rm XOR}\ y$ を $x\verb|^|y$ と書き,ビットシフト $x \times 2^y$ を $x\verb|<<|y$ と書く.
$2$ 進数で書かれた整数 $A,B$ が与えられるので,
$\displaystyle \qquad \sum_{i=0}^{314159} (A \verb|^| (B \verb|<<| i))$
の値を ${\rm mod}\ 1000000007\ (10^9+7)$ で求める問題.
$\displaystyle \qquad \sum_{i=0}^{314159} (A + (B \verb|<<| i))$
を計算して,足しすぎている
$\displaystyle \qquad 2\sum_{i=0}^{314159} (A \verb|&| (B \verb|<<| i))$
を引くことを考える.
$1$ つ目の式は,$A,B$ のビットが $1$ の各桁ごとに,どれぐらいの値が足されるかを考えて計算すれば簡単にできる.
$2$ つ目の式は,$A$ のビットが $1$ の各桁に着目して,その桁がどのぐらい結果に貢献するかというと,何桁目かというとの,$B$ の該当する桁とその後ろに何回 $1$ の桁が登場するかによる.
よって,$B$ において,$1$ の桁が出現した回数の累積和を求めておけば計算できる.
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
#define ll long long
#define MD 1000000007
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}return s;}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}
int As, Bs;
char A[300000], B[300000];
ll pw[1000000];
ll valA, valB;
int main(){
int i, j, k, cnt;
int N = 262144;
ll res;
As = reader(A);
Bs = reader(B);
pw[0] = 1;
REP(i,1,500000) pw[i] = (pw[i-1] * 2) % MD;
valA = valB = 0;
rep(i,As) valA = (valA * 2 + A[i]-'0') % MD;
rep(i,Bs) valB = (valB * 2 + B[i]-'0') % MD;
res = 0;
rep(i,314159+1) res = (res + valA) % MD;
rep(i,314159+1) res = (res + valB * pw[i]) % MD;
cnt = 0;
rep(i,As){
if(i < Bs && B[Bs-1-i]=='1') cnt++;
if(A[As-1-i]=='1'){
res = (res - 2 * cnt * pw[i]) % MD;
}
}
res %= MD;
if(res < 0) res += MD;
writer((int)res, '\n');
return 0;
}
Current time: 2024年04月20日15時20分42秒
Last modified: 2014年11月18日04時15分06秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_101jul14
トップページに戻る
Logged in as: unknown user (not login)