小红书 9.10笔试

编程题三道：

1.给一个数n，如果有连续的x*(x+1)*(x+2)....这种公差为1的数（至少3个）相乘刚好为n，则称之为“好数”；判断YES or NO

2.之前原题，01字符串更改，输出最少 [ L , R ] 更改数 使得整体字符串回文；

3.给定一个数n（小于10^18），计算，其中highdig定义为 i 的二进制表示中最高位 1 所在的位置：比如3：11，highdig(3)就是2。最后结果对998244353取余。

MD差一点点就写出来了，最后求和的时候少写了一个 +1 啊。

下面给出我（认为）的正确代码：

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
    int T = 0;
    cin >> T;

    vector<long long> doubles(61, 0);

    for (int i = 0; i < 61; i++) {
        doubles[i] = (long long)pow(2, i);
    }

    vector<long long> sums(61, 0);
    for (int i = 1; i < 61; i++) {
        sums[i] = sums[i - 1] + i * (((doubles[i] - 1) + doubles[i - 1])%998244353) * ((doubles[i] - doubles[i - 1])%998244353) / 2;
        if (sums[i] >= 998244353) sums[i] = sums[i] % 998244353;
    }

    while (T--) {
        long long n;
        cin >> n;
        int x = 0;
        for (int i = 0; i < 61; i++) {
            if (n < doubles[i]) {
                x = i;
                break;
            }
        }

        long long res = sums[x - 1] + (long long)x * (n - doubles[x - 1]+1) * (n + doubles[x - 1]) / (long long)2;

        cout << res % 998244353 << endl;
    }
    return 0;
}

还有选择题20道，大部分与机器学习（深度学习）相关。还有一个构建哈夫曼树什么的。