小编squ*_*001的帖子

有没有算法算(1^x + 2^x + 3^x + ... + n^x) mod 1000000007？
注意:a^b是a的b次方.

约束是1 <= n <= 10^16, 1 <= x <= 1000.所以N的值非常大.

我只能解决O(m log m)if m = 1000000007.它非常慢,因为时间限制是2秒.

你有任何有效的算法吗？

有评论说它可能与这个问题重复,但它肯定是不同的.

对于给定的整数,n并m确定x^mterm in的系数(x^2+x+1)^n是偶数还是奇数？

例如,如果n = 3且m = 4 (x^2+x+1)^3 = x^6 + 3x^5 + [[6x^4]] + 7x^3 + 6x^2 + 3x + 1,那么项的系数x^4是6(=偶数).

n并且m大到10 ^ 12并且我想在几秒钟内计算,因此您无法在线性时间内计算.

你有任何有效的算法吗？

我对这个问题有疑问.

题

• 您将获得一个序列a[0], a 1],..., a[N-1]和一组范围(l[i], r[i]) (0 <= i <= Q - 1).
• 计算mex(a[l[i]], a[l[i] + 1],..., a[r[i] - 1])所有(l[i], r[i]).

函数mex是最小排除值.
维基百科的mex函数页面

你可以认为N <= 100000, Q <= 100000, and a[i] <= 100000.
O(N * (r[i] - l[i]) log(r[i] - l[i]) )算法很明显,但效率不高.

我目前的方法

#include <bits/stdc++.h>
using namespace std;
int N, Q, a[100009], l, r;
int main() {
    cin >> N >> Q;
    for(int i = 0; i < …

我想知道什么

我想问一下以下两个问题.

• 在C++中std :: priority_queue中使用了什么类型的堆？
• top(), pop(), push()在C++中std :: priority_queue 的操作时间复杂度是多少？

我在互联网上查了一下,但我找不到答案.
请告诉我答案.如果你不知道C++中的所有版本,请告诉我GCC C++ 11或C++ 14的答案.

我为什么需要

我想实现Dijkstra算法的最短路径问题.

让number of vertex = |V|, number of edge = |E|图中的.
时间复杂性是O(|E| log |V|)使用二进制堆.
但时间的复杂性在于O(|E| + |V| log |V|)使用Fibonacci Heap.

如您所见,如果图形密集,时间会有很大差异.
实际上,有O(|V|^2)没有使用堆的算法,所以我也想知道我是否必须实现它.

我的实施

这是我使用Binary Heap实现优先级队列.
insert(x)等于push(x),extract()等于top() --> pop().
但是std :: priority_queue远比我的实现快得多.

#include <vector>
#include <algorithm>
using namespace std;
template<class …

我学习了 Fenwick Tree 算法，上面写着“i & (-i) 等于最右边的位”。
例如，3 & (-3) = 1, 48 & (-48) = 16.。

我测试了 的结果i <= 64，所有值都满足条件。
但我不知道为什么所有正整数 i 的条件都满足（证明）。

请告诉我如何证明。

编辑：您可以假设 i 是 32 位整数（但 16 位也可以）。如果是，则 i 的取值范围为1 <= i <= 2^31-1。

我想知道解决这个问题的有效方法：

给定具有左上角和右下角的 N 个矩形，请找出 N 个矩形的并集的周长。

我只有O(N^2)算法而且太慢了，所以请找到更有效的算法。

您可以假设坐标值为正整数且小于 100000。

编辑：例如，在这种情况下，周长是 30。

一个 O(n^2) 算法：

for x=0 to maxx
   for i=0 to N
      if lowx[i] = x
         for j=lowy[i] to highy[i]
            d[j]++
            if d[j] = 1 then ret++
      if highy[i] = x
         for j=lowy[i] to highy[i]
            d[j]--
            if d[j] = 0 then ret++
   for y=0 to maxy
      if d[y] = 0 && d[y + 1] >= 1 then ret++
      if d[y] >= 1 && d[y + 1] = 0 …

我想解决这个问题：

对于给定的序列 ，a[0], a[1], a[2],..., a[n-1]请找到该序列的“周期”。
周期是对于所有有效 i 满足 a[i] = a[i+k] 的最小整数 k (k >= 1)，并且 k 是 n 的除数。

我当前的解决方案是计算 n 的所有除数（这是 k）并测试所有 k，但这需要O(n * d(n)). 我认为这很慢。
有没有高效的算法？