Привет. Помогите в решении этой задачи. Есть офф, решение, которое я все равно не понимаю,
#include <bits/stdc++.h>
using namespace std;
static const int mod = 1000000000 + 7;
static int pow2(int degree) {
long long accum = 2;
long long res = 1;
for (int i = 0; i < 31; i++) {
if (degree & (1 << i))
res = res * accum % mod;
accum = accum * accum % mod;
}
return res % mod;
}
int main() {
int k;
scanf("%d", &k);
int degree = k - (k & (k - 1));
int res = (pow2(degree) + mod - 1) % mod;
printf("%d", res);
return 0;
}
Вот не люблю битовые операции). Могу решить задачи сложнее на другие темы, но только не битовые операции)
Всех благодарю
Не знаю, как доказать решение, но мне помогло в данной задаче посмотреть что происходит для небольших чисел(<=100000) , можешь написать программку и посмотреть, сколько действий требуется, чтобы прийти из x в x по алгоритму для каждого x от 1 до n. Там есть закономерность. Если что-то непонятно, можешь глянуть мое решение. https://codeforces.net/gym/101446/submission/68125746
Действительно, перебрав числа до 100 можно найти закономерность. Для чисел, которые является степенями двойки — ответ два в степени числа — 1, Для оставшихся чисел надо найти наибольшее число, также являющееся степенью двойки, на которое они делятся без остатка, И ответ будет такой же как и для этой степени. Это все конечно круто, но мне больше нравятся задачи где можно доказать)). Тут конечно можно, но слишком сложно, так что, думаю, все решили без доказательства по принципу "Ну видно же", как в еще одной такой задаче .
Ну вроде классический мотив. Сперва понимаем что f(a xor b)=f(a) xor f(b), потом понимаем (например по индукции) куда переходит число за 2**k итераций. То есть понятно как по числу понять за сколько он зациклится(2**кол-во бит в нем). Дальше нужно найти кол-во тех, для которых k из условия это цикл.