草庐IT

c++ - 计算可被 K 整除的子数组

coder 2023-11-15 原文

给定一个包含 n 个正整数的序列，我们需要计算其和能被 k 整除的连续子序列。

约束:N 最大为 10^6，每个元素最大为 10^9，K 最大为 100

示例:设 N=5 和 K=3，数组为 1 2 3 4 1

这里的答案是4

解释:存在4个总和能被3整除的子序列，它们是

3
1 2
1 2 3
2 3 4

我的尝试:

long long int count=0;
for(int i=0;i<n;i++){
    long long int sum=0;
    for(int j=i;j<n;j++)
    {
        sum=sum+arr[j];
        if(sum%k==0)
        {
            count++;
        }
    }
}

但显然它的方法很糟糕。他们可以更好地解决这个问题吗？请帮忙。

完成问题:https://www.hackerrank.com/contests/w6/challenges/consecutive-subsequences

最佳答案

这是一个快速的 O(n + k) 解决方案:

1)让我们计算前缀和 pref[i](对于 0 <= i=""><>

2) 现在我们可以计算 count[i] - 总和为 i 模 k(0 <= i="">< k)="" 的前缀数。="" 这可以通过遍历所有前缀并使="" count[pref[i]="" %="" k]++="" 来完成。="" 最初，count[0]="1(空前缀的总和为" 0)和="" 0="" for="" i="" !="">

3)答案是对所有 i 求和 count[i] * (count[i] - 1)/2。

4)最好计算前缀和模k以避免溢出。

为什么有效？让我们仔细看看可被 k 整除的子数组。假设它从 L 位置开始到 R 位置结束。它可以被 k 整除当且仅当 pref[L - 1] == pref[R](模 k)因为它们的差是零模 k(根据可整除性的定义)。因此，对于每个固定模数，我们可以选择任意两个具有此前缀和模 k 的前缀(并且正好有 count[i] * (count[i] - 1)/2 种方法可以做到这一点)。

这是我的代码:

long long get_count(const vector<int>& vec, int k) {
  //Initialize count array.
  vector<int> cnt_mod(k, 0);
  cnt_mod[0] = 1;
  int pref_sum = 0;
  //Iterate over the input sequence.
  for (int elem : vec) {
    pref_sum += elem;
    pref_sum %= k;
    cnt_mod[pref_sum]++;
  }
  //Compute the answer.
  long long res = 0;
  for (int mod = 0; mod < k; mod++)
    res += (long long)cnt_mod[mod] * (cnt_mod[mod] - 1) / 2;
  return res;
}

关于c++ - 计算可被 K 整除的子数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/24518682/

amp43countsectionlongc++algorithm

有关c++ - 计算可被 K 整除的子数组的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby-on-rails - 使用一系列等级计算字母等级 - 2

    这里是Ruby新手。完成一些练习后碰壁了。练习:计算一系列成绩的字母等级创建一个方法get_grade来接受测试分数数组。数组中的每个分数应介于0和100之间，其中100是最大分数。计算平均分并将字母等级作为字符串返回，即“A”、“B”、“C”、“D”、“E”或“F”。我一直返回错误:avg.rb:1:syntaxerror,unexpectedtLBRACK,expecting')'defget_grade([100,90,80])^avg.rb:1:syntaxerror,unexpected')',expecting$end这是我目前所拥有的。我想坚持使用下面的方法或.join，

  3. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  4. 计算机毕业设计ssm+vue基本微信小程序的小学生兴趣延时班预约小程序 - 2

    项目介绍随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱小学生兴趣延时班预约小程序的设计与开发被用户普遍使用,为方便用户能够可以随时进行小学生兴趣延时班预约小程序的设计与开发的数据信息管理,特开发了小程序的设计与开发的管理系统。小学生兴趣延时班预约小程序的设计与开发的开发利用现有的成熟技术参考,以源代码为模板,分析功能调整与小学生兴趣延时班预约小程序的设计与开发的实际需求相结合,讨论了小学生兴趣延时班预约小程序的设计与开发的使用。开发环境开发说明：前端使用微信微信小程序开发工具：后端使用ssm：VU

  5. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  6. ruby - 是否有内置的 Ruby 1.8.7 将数组拆分为相同大小的子数组？ - 2

    我已经开始了:defsplit_array(array,size)index=0results=[]ifsize>0whileindex如果我在[1,2,3,4,5,6]上运行它，比如split_array([1,2,3,4,5,6],3)它将产生这个数组:[[1,2,3],[4,5,6]]。在Ruby1.8.7中是否已经有可用的东西可以做到这一点？ 最佳答案 [1,2,3,4,5,6].each_slice(3).to_a#=>[[1,2,3],[4,5,6]]对于1.8.6:require'enumerator'[1,2,3,4

  7. ruby - 使用 Ruby，计算 n x m 数组的每一列中有多少个 true 的简单方法是什么？ - 2

    给定一个nxmbool数组:[[true,true,false],[false,true,true],[false,true,true]]有什么简单的方法可以返回“该列中有多少个true？”结果应该是[1,3,2] 最佳答案 使用转置得到一个数组，其中每个子数组代表一列，然后将每一列映射到其中的true数:arr.transpose.map{|subarr|subarr.count(true)}这是一个带有inject的版本，应该在1.8.6上运行，没有任何依赖:arr.transpose.map{|subarr|subarr.in

  8. arrays - 计算数组中的匹配元素 - 2

    给定两个大小相等的数组，如何找到不考虑位置的匹配元素的数量？例如:[0,0,5]和[0,5,5]将返回2的匹配项，因为有一个0和一个5共同；[1,0,0,3]和[0,0,1,4]将返回3的匹配项，因为0有两场，1有一场；[1,2,2,3]和[1,2,3,4]将返回3的匹配项。我尝试了很多想法，但它们都变得相当粗糙和令人费解。我猜想有一些不错的Ruby习惯用法，或者可能是一个正则表达式，可以很好地回答这个解决方案。 最佳答案 您可以使用count完成它:a.count{|e|index=b.index(e)andb.delete_at

  9. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  10. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

随机推荐