OUPC betaに参加しました
2020/3/21
#HackerRank #有志コン
コンテストへのリンク
解説まとめ
B Doubling Step
code:cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
typedef long long ll;
struct mint {
/*省略*/
}
};
ll N;
vector<mint> dp;
vector<bool> visited;
mint dfs(ll X){
if(visitedX){
return dpX;
}
mint res = 0;
for(ll i = 1; i < X;i *= 2){
res += dfs(X - i);
}
visitedX = true;
return dpX = res;
}
int main() {
cin >> N;
dp.assign(N + 5, 0);
visited.assign(N+5, false);
dp1 = 1;
visited1 = true;
cout << dfs(N) << endl;
}