题解：P11397 界分数

huluwahmh · 2024-12-19 22:04:56 · 题解

看前人的题解我是一头雾水。

我来水写一篇通俗易懂的题解。

明确策略

首先，约掉 2 的利益是最大的，这不难理解：

每执行一次操作（除第一次操作），都能约掉一个 2，所以，如果每一次操作都约掉一个 2，那么共执行 \log_2n 次操作。如果说要约掉一个 3，那么至少要执行两次操作，但如果这两次操作每次约掉一个 2，则相当于约了一个 4，显然利益更大；同理，要约掉一个 4，就要执行三次操作，也没有约 2 的利益大。以此类推，可知约掉 2 的利益是最大的。

每一次都必然能约掉一个 2，这也不难理解，只需：当分母为奇数，执行操作 2；反之，执行操作 1。

其次，再考虑第一次操作，应执行操作一，下面给出样例解释。

显然，先执行操作 2 可能会多执行一次操作。

那么，我们的策略就是：第一步执行操作 1，之后分母为偶执行执行操作 1，分母为奇执行执行操作 2。

计算过程

已经明确了策略，下一步就是如何计算了。

直接模拟很显然会 TLE，那就要用数学方法。

已经知道执行步数是 \left(\log_2 n \right)+ 1，但若是每个数都进行计算，还是会 TLE。

所以，这道题旨在减少计算。那就来找一找规律：

这样看可能不太明显，我们换一种方式：

1. 1 = 1\\
2. 2 = 1 + 1\\
3. 3 = 1 + 1 + 1\\
4. 3 = 1 + 1 + 1\\
5. 4 = 1 + 1 + 1 + 1\\
6. 4 = 1 + 1 + 1 + 1\\
7. 4 = 1 + 1 + 1 + 1\\
8. 4 = 1 + 1 + 1 + 1\\
9. 5 = 1 + 1 + 1 + 1 + 1\\

这么看来，我们可以竖着加，即每遇到一个 2 的倍数 t，就加 n - t。这样，可以大大减小时间复杂度。

#include<bits/stdc++.h>
#define int long long//即所有的int变成long long 
using namespace std;

int Mod = 998244353;

signed main()//由于有 int long long，所以此处改为signed 
{
    int n,t = 1;
    cin >> n;
    int s = n;
    while(pow(2,t - 1) < n)
    {
        t++;
        s += n - pow(2,t - 1);
        s %= Mod;
    }
    cout << s % Mod << endl;
    return 0;
}

但是，新的问题又出现了：我们可以通过前面的测试点，但最后一个 subtask 会 WA。那只有可能是在 \bmod \ 998244353 时出现了问题。仔细观察可以发现，最后一个 subtask 的数据超极大，直接加减会超出 long long 数据类型的范围。所以，要稍作改动，先 \bmod\ 998244353，再加减。

#include<bits/stdc++.h>
#define int long long//即所有的int变成long long 
using namespace std;

int Mod = 998244353;

signed main()//由于有 int long long，所以此处改为signed 
{
    int n,t = 1;
    cin >> n;
    int s = n;
    while(pow(2,t - 1) < n)
    {
        int x = pow(2,t - 1);//pow函数返回值是double类型，要转成long long 
        s += (n - x) % Mod;
        t++;
    }
    cout << s % Mod << endl;
    return 0;
}