HackerRank 101 Hack July'14 3問目 - Xor and Sum

Source

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$ の桁が出現した回数の累積和を求めておけば計算できる．

C++によるスパゲッティなソースコード

#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月19日12時47分11秒
Last modified: 2014年11月18日04時15分06秒 (by laycrs)
Tags: Competitive_Programming HackerRank HackerRank_101jul14
トップページに戻る

Logged in as: unknown user (not login)

ログイン：