时间戳

首页 > 解决方案 > 针对给定问题的优化算法？

c++ - 针对给定问题的优化算法？

问题描述

我正在解决一个问题，该问题表明我们有一个包含从 1 到 N 的整数的列表 L。我们必须执行以下操作 N-1 次：

  1. 选择列表中的两个元素，我们用 X 和 Y 来表示它们。
  2. 从 L 中删除选定的元素。
  3. 将数字 X + Y + X*Y 附加到 L。最后，L 正好包含一个整数。找到这个整数。由于答案可能很大，我们必须以 10^9 + 7 为模计算它

约束：1≤N≤1,000,000

时间限制：1秒

我编写了这段代码，它在线性时间内给出了正确的答案，但它说这种方法超出了时间限制。有人可以提供更好的优化解决方案吗

inline ull cal(ull x, ull y){
  ull ans, i, modno;
  modno = 1000000007;
  i = 1;

  ans = (x + y);
  i = (i*x) % modno;
  i = (i*y) % modno;
  ans = ans + i;
  ans = ans % modno;
  return ans;
}

int main(){
    ull n;
    cin>>n;

    ull sum, modno;
    sum = 0;
    modno = 1000000007;

    if(n == 1)
        cout<<1<<endl;
    else
    {
        sum = n + (n-1) + (n*(n-1));
        n -= 2;
        do
        {
            if(n <= 0)
                break;

            sum = cal(sum, n);
            n -= 1;
        }while(1);
        cout<<ans<<endl;
     }

   return 0;
}

最终代码：

    ull n;
    cin>>n;

    if(n == 1)
        cout<<1<<endl;
    else
    {
        ull modno = 1000000007;
        ull ans = 1;
        ull no = n+1;

        while(no >= 1)
        {
            ans = (ans*no);
            if(ans > modno)
                ans = ans%modno;
            no--;
        }

        ans = ans - 1;
        ans = ans % modno;
        cout<<ans<<endl;

标签： c++optimization

解决方案

总和有一个封闭形式的解决方案：L = (N+1)!-1

总和遵循这个循环方程L_N = N + L_(n-1) + N*L_(n-1), L_0=0，可以通过简单地总是选择X=L_(N-1)和Y=N（=要添加的下一个数字）来获得。

推导：

推导

编辑：

当您发布最终代码时，我正在发布我的基准：

#include <iostream>
#include <cstdint>
#include <chrono>

std::uint64_t
factorial(std::uint64_t n) {
    std::uint64_t x = 1;
    while (n > 1)
        x = (x * n--) % 1'000'000'007;
    return x;
}
int
main() {
    std::uint64_t n;
    std::cin >> n;
    std::uint64_t numMicro = 0;
    for (std::size_t i = 0; i < 1'000; ++i) {
        auto start = std::chrono::high_resolution_clock::now();
        volatile std::uint64_t res = factorial(n);
        auto end = std::chrono::high_resolution_clock::now();
        numMicro +=
            std::chrono::duration_cast<std::chrono::microseconds>(end - start)
                .count();
    }
    std::cout << "On average: " << numMicro / 1000.0 << "microseconds";
    return 0;
}

用 编译-O3，volatile只是为了确保编译器不会优化计算。您的解决方案几乎相同，低于 1 秒。不确定要进一步优化什么。

推荐阅读