时间戳

首页 > 解决方案 > 使用 ``1ll<<(N-1)`` 将大量值分配给 long long int 变量

c++ - 使用 ``1ll<<(N-1)`` 将大量值分配给 long long int 变量

问题描述

我看到的问题是：给你一个大小为N的数组A。如果元素Ai的值 ( Ai ) 大于或等于Ki并且Ki是包含元素Ai的数组A的子集的总数，则称元素 Ai 被充电。

逻辑只是一个数字作为子集出现的次数是 2^N-1 次。但在某些测试用例中，N 为 4000+。因此， 2^N-1 将远远超出任何变量类型所能容纳的范围，但在社论中，作者使用了1ll<<(N-1). 我知道左移运算符是X<<Y = X*2^Y. 但是这个1ll是什么？它如何能够存储如此大的价值？

#include <bits/stdc++.h>

#define M 1000000007

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    int N;
    cin >> N;
    long long arr[N];
    for (int i = 0; i < N; i++)
      cin >> arr[i];
    if (N >= 64)
      cout << 0 << endl;
    else {
      long long val = (1ll << (N - 1));
      long long ans = 0;
      for (int i = 0; i < N; i++)
        if (arr[i] >= val)
          ans = (ans + arr[i] % M) % M;
      cout << ans << endl;
    }
  }
}

1<<N-1解释2^N-1但 1ll 是否意味着它可能需要很长很长的时间和long long val = 1ll<<N-1；意味着它可以达到128位？

标签： c++arraysbitwise-operatorsunsigned-long-long-int

解决方案

但这是什么1ll？

是1ll一个整数文字。1是一个十进制文字并且ll是一个整数后缀。后缀ll表示整型文字的类型是long long int. 这1意味着文字的值是，嗯，1。

它如何能够存储如此大的价值？

我想你是在问这条线：

long long val = (1ll << (N - 1));

因为if (N >= 64) .. else之前，我们知道N < 64。所以最大数量可能是：

1ll << 63 - 1   =
1ll << 62       =
0x4000000000000000

这只是一个适合long long int类型的数字。该long long int类型至少有 64 位。

如果没有ll后缀，1则将具有类型int。在int类型比 64 位更窄的架构上，例如。16 位，然后会发生未定义的行为。将变量左移一个大于或等于左操作数位长度的数字是未定义的行为，请参见前。这个问题。

如果您询问该行：

ans = (ans + arr[i] % M) % M;

它正在计算和模#define M 1000000007。做作业/家庭作业以这个数字为模来计算总和是很常见的，参见 ex this或this。该算法计算总和模 1000000007，而不是整数，这就是它能够将其存储在long long变量中的原因。

推荐阅读