#bit mask

[copingwithcoding]

12/100: I studied a good bit and my interview went well, I think! I realized that there was a better way to solve the problem after the interview. So, I went and implemented that and emailed the better solution to my interviewer. I felt good about studying and really knowing my stuff. 

Stationery:

BIC brite liner in Green

Pilot G-2 0.7 in Teal 

Dayal (4G) 0.5mm in Black 

🎧 Trndsttr [M. Maggie, Black Coast] 

[yt-siden-algo]

CTPC:G Lucky Number

解法

ビットマスクを利用する．すなわち，\( n \)番目の数は， \[ a(i) = 7^i \hspace{1em} (for \hspace{1ex} i \ge 0),\hspace{1em} N = \lceil \log_2n \rceil \hspace{1em} (for \hspace{1ex} n \ge 1) \] とすると， \[ \sum_{i=0}^{N-1} {f(i,n)}, \hspace{1em} where \hspace{1ex} f(i,n) = \left\{ \begin{array}{cc} a(i) & n \& (1 \ll i) \neq 0 \\\\ 0 & otherwise \end{array} \right. \] で表される．(\( \& \)はビット論理積，\( \ll \)はビット左シフトとします) あと，求めるものは\( 10^6 \)のmodなので\( a(i) \)もmodで求めておく．

コード

#include <iostream> using namespace std; typedef long long ll; const int MOD = 1000000; int main() { ll n; cin >> n; ll N=1; while ((1<<(N-1)) < n) { N++; } ll a[N]; a[0] = 1; for (ll i=1; i<N; i++) { a[i] = a[i-1] * 7; a[i] %= MOD; } ll ans = 0; for (int i=0; i<N; i++) if (n&(1<<i)) ans = (ans + a[i]) % MOD; cout << ans << endl; }