时间戳

首页 > 解决方案 > 为什么位操作不适用于 CSES 位字符串问题

c++ - 为什么位操作不适用于 CSES 位字符串问题

问题描述

问题说明要打印大小为 n 的位串的数量。在数学上，答案只是 2^n，但因为 n 可以从 1 到 10^6，所以答案必须是更大尺寸的数据类型。这是我的程序：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int MOD = (int)1e9 + 7;

int main()
{
    int n;
    cin >> n;
    cout << ((1ULL << n) % MOD);
}

我什至尝试使用 LL、ULL，甚至尝试制作 n ull 或 ll。但是这些方法都不起作用。有人可以解释为什么吗？ULL 的范围还不够大吗？在某些解决方案中，我看到了一个 for 循环，其中答案在循环的每次迭代中乘以 2 和 mod MOD：

for(int i = 0; i<n; i++) ans = ans*2 % ((int)1e9 + 7)

这不会给出错误的答案，因为如果在循环的某个迭代中的某个地方，答案高于 MOD，它将成为 MOD 的剩余部分，然后再次开始乘以 2。正确的答案不是首先找到答案，然后通过 MOD 修改它？使用循环方式，它将继续对 REMAINDER 求幂，我不明白它是如何成为正确答案的。

标签： c++algorithminteger-overflow

解决方案

要回答您的第一个问题，不，ULL 还不够大。

回想一下 unsigned long long 通常是 64 位大，所以你不可能在不溢出的情况下移动 1 10^6 位。

这个问题的解决方案是通过平方和每一步取模来求幂；使用 a*a % mod = (a%mod) * (a%mod) 的属性。这解决了 log(10^6) 时间的问题。

看看这个：https ://www.geeksforgeeks.org/exponential-squaring-fast-modulo-multiplication/

推荐阅读