Redaksiya

Let's begin by calculating the maximum value of $f(x,y)$ where $0\le x$, $y\le 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\le x$ and $a\le 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\ast (2\ast a-1)$.

Let's denote $mx$ as the maximum value of $f$, which equals $2\ast (2\ast a-1)$.

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

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

2)Second case , $x\ne 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\le 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\ne 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 $mx$.

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$ ; $last$_$bit$].

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 $\le 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(lo{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(lo{g}^3)$ or $O(lo{g}^2)$ or $O(lo{g}^2)$

Memory complexity: $O(log)$

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