Разбор

Problem Author:	Illia Shevchenko
Prepared by:	Illia Shevchenko , Illia Fursov
Editorial by:	Illia Shevchenko

Let's begin by calculating the maximum value of $f (x, y)$ where $0 \leq x$ , $y \leq n$ .

$f (x, y) = (x \oplus y) + (x ∣ y) + (x & y),$

We can calculate $f$ for each bit separately.

Let's see how the values of $x$ and $y$ in bit $i$ affect $f (x, y)$ :

1) If the value of $x$ is $0$ and the value of $y$ is $0$ , then $f (x, y) = 0$ .

2) If the value of $x$ is $0$ and the value of $y$ is $1$ , then $f (x, y) = 2^{i} + 0 + 2^{i} = 2^{i + 1}$ .

3) If the value of $x$ is $1$ and the value of $y$ is $0$ , then $f (x, y) = 2^{i} + 0 + 2^{i} = 2^{i + 1}$ .

4) If the value of $x$ is $1$ and the value of $y$ is $1$ , then $f (x, y) = 2^{i} + 2^{i} + 0 = 2^{i + 1}$ .

Let $a$ be the maximum power of $2$ such that $a \leq x$ and $a \leq y$ .

The maximum value of $f$ will be achieved when there is at least one set bit in every bit position up to $a$ in either $x$ or $y$ .

For example, take the numbers $a$ and $a - 1$ .

$f (a, a - 1) = 2 * (2 * a - 1)$ .

Let's denote $m x$ as the maximum value of $f$ , which equals $2 * (2 * a - 1)$ .

1)First case , $x == y$ .

$f (x, x) == m x$ . This is possible only if $n = 2 * a - 1$ , and there is only one such case.

2)Second case , $x \neq = y$ .

Now, let's apply a standard idea: consider the length of the maximum common prefix of $x$ and $n$ , and the length of the maximum common prefix of $y$ and $n$ .

Let the maximum common prefix of $x$ and $n$ be $i$ , and the maximum common prefix of $y$ and $n$ be $j$ .

Then, the $i + 1$ bit in $x$ and $n$ does not match (otherwise, we could extend the common prefix). But since $x \leq n$ , the $i + 1$ bit in $x$ is $0$ , and the $i + 1$ bit in $n$ is $1$ .

We do the same for $y$ .

Now there are two cases:

1) $i == j$ .

2) $i \neq = j$ .

1)If $i == j$ , then both $x$ and $y$ will have a $0$ in the $i + 1$ bit, so the result will be less than $m x$ .

2)Let's consider the case $i > j$ (the case $i < j$ is analogous).

Thus, we have two prefixes: $i$ and $j$ .

Notice that there should be no zeroes in the prefix of length $j$ .

Also, notice that the $i + 1$ bit in $y$ must be $1$ since the $i + 1$ bit in $x$ is $0$ .

Now we have two separate non-overlapping bit segments: $[j + 2; i]$ and [ $i + 2$ ; $l a s t$ _ $bi t$ ].

We can count the number of possible ways to assign bits in both of these segments and then multiply the results.

Let's consider a bit $k$ belonging to the segment [ $j + 2$ ; $i$ ]. If it is $0$ , then the bit in $y$ must be $1$ ; if it is $1$ , then there are two options for the bit in $y$ .

Now let's consider the segment [ $i + 2$ ; $0$ ]. Since $x$ and $y$ are already $\leq n$ , we can place the bits as we like, as long as there is at least one $1$ in one of the numbers. This can be done in $3$ ways raised to the power of the length of the segment.

Full solution with $O (l o g^{3})$ time complexity (C++):

/*
In honor of Anton Tsypko
*/

#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cmath>
#include <random>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <bitset>
#include <cmath>

using namespace std;

int log_ = 3;
int inf = 2000000007;
int mod = 1000000007;

int p = 501;


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    long long n;
    cin >> n;

    long long a = 1;

    int c = 0;

    while (a * 2 <= n)
    {
        a *= 2;
        c++;
    }
    long long mx = 2 * (2*a - 1);

    vector <int> bit;


    long long n_ = n;
    while (n_ > 0)
    {
        bit.push_back(n_ % 2);
        n_ /= 2;
    }

    bit.push_back(5);
    reverse(bit.begin() , bit.end());


    long long ans = 0;
    for (int i = 0; i <= c+1; i++)
    {
        for (int j = 0; j <= c + 1; j++)
        {

            if (bit[j] == 0)
                break;

            if (i + j == 0)
                continue;
            
            if (i < j)
                continue;
            
            if (i == j)
                continue;
            
            if ((i + 1 < bit.size()) and (bit[i + 1] == 0))
                continue;
            
            if ((j + 1 < bit.size()) and (bit[j + 1] == 0))
                continue;
            

            long long col = 1;

            for (int k = j + 2; k <= i; k++)
            {
                if (bit[k] == 1)
                    col *= 2;

                col %= mod;
            }

            for (int k = i+2; k < bit.size(); k++)
            {
                col *= 3;

                col %= mod;
            }

            ans += col;
            ans %= mod;
        }
    }

    ans *= 2;

    if (2 * n == mx)
        ans++;

    cout << mx << " " << ans % mod;
}

Time complexity: $O (l o g^{3})$ or $O (l o g^{2})$ or $O (l o g^{2})$

Memory complexity: $O (l o g)$

There is also a solution using dynamic programming with a time complexity of $O (lo g)$ .