[此贴子已经被作者于2022-7-25 19:21编辑过]

程序代码：

#include <iostream>
#include <functional>
#include <chrono>
#include <format>

template<class F, class... Args>
constexpr std::invoke_result_t<F,Args...> elapsed_time( F&& f, Args&&... args ) noexcept(std::is_nothrow_invocable_v<F, Args...>)
{
    using namespace std::chrono;

    auto format_duration = []( const auto& dur ) noexcept(true)
    {
        auto ns = duration_cast<nanoseconds>(dur).count();
        std::cout << std::format( "elapsed time: {:02}:{:02}:{:02}.{:03}'{:03}'{:03}"
            , ns/3600000000000
            , ns%3600000000000/60000000000
            , ns%60000000000/1000000000
            , ns%1000000000/1000000
            , ns%1000000/1000
            , ns%1000/1 ) << " (" << dur << ")\n";
    };

    auto t_start = high_resolution_clock::now();
    if constexpr ( std::is_void_v<std::invoke_result_t<F,Args...>> )
    {
        std::invoke( std::forward<F>(f), std::forward<Args>(args)... );
        auto t_end = high_resolution_clock::now();
        format_duration( t_end-t_start );
    }
    else
    {
        auto result = std::invoke( std::forward<F>(f), std::forward<Args>(args)... );
        auto t_end = high_resolution_clock::now();
        format_duration( t_end-t_start );
        return result;
    }
}

//#include <limits>
#include <bit>
#include <cassert>
using namespace std;

constexpr unsigned long long foo( unsigned n ) noexcept(true)
{
    // 从高位到地位依次检查是否存在三个连续的相同序列
    auto triple = []( unsigned long long m, int fp=std::numeric_limits<int>::max() ) noexcept(true) -> int
    {
        const int bs = (int)std::bit_width( m ); // 此序列m的位数
        for( int i=std::min(bs-3,fp); i>=0; --i )
        {
            for( int w=1; w<=(bs-i)/3; ++w )
            {
                auto a = (m>>(i+0*w)) & ((1ull<<w)-1);
                auto b = (m>>(i+1*w)) & ((1ull<<w)-1);
                auto c = (m>>(i+2*w)) & ((1ull<<w)-1);
                if( a==b && b==c )
                    return i;
            }
        }
        return -1;
    };

    if( n == 0 )
        return 1;
    assert( n <= std::numeric_limits<unsigned long long>::digits );
    unsigned long long count = 0;
    for( unsigned long long i=(1ull<<(n-1)); ((i>>(n-1))&1)!=0; ++i ) // 因为“0变为1，1变为0，是两个等价的序列”，所以只取1开头的序列即可
    {
        int r = triple( i, (int)std::bit_width(i^(i-1))-1 );
        if( r == -1 )
            ++count;
        else
            i |= (1ull<<r)-1;
    }

    return 2*count;
}

constexpr void test( unsigned n ) noexcept(true)
{
    for( unsigned i=0; i<=n; ++i )
        cout << "foo(" << i << ") = " << foo(i) << '\n';
}

int main( void )
{
    elapsed_time( test, 40 );
}

程序代码：

#include <stdio.h>

int main( void )
{
    unsigned n;
    scanf( "%u", &n );

    const unsigned map[] = { 1, 2, 4, 6, 10, 16, 24, 36, 56, 80, 118, 174, 254, 378, 554, 802, 1168, 1716, 2502, 3650, 5324, 7754, 11320, 16502, 24054, 35058, 51144, 74540, 108664, 158372, 230800, 336480, 490458, 714856, 1041910, 1518840, 2213868, 3226896, 4703372, 6855388, 9992596 };
    printf( "%u\n", map[n] );
}