Skip to content

Latest commit

 

History

History
24 lines (19 loc) · 1.79 KB

pow_with_mod_in_python.md

File metadata and controls

24 lines (19 loc) · 1.79 KB

1498. Number of Subsequences That Satisfy the Given Sum Condition

这一题作为周赛的第三道,猛地一下把我给弄懵了。 我很怕遇到这种需要mod 10^9+7的题。 感觉会很复杂。

我努力控制住紧张的情绪,尝试着梳理。

  1. 首先我想是否可以用dp的方法,但是发现dp[i] 和 dp[i+1]之间没有简明的转换关系,根据以往的经验,果断放弃 这个思路
  2. 然后我开始尝试先思考整个数组作为subsequence,然后发现这里面只需要关注min和max,然后如果min + max之和 大于target那么max一定不能出现在subsequence中,然后有了这个思路,我想用heap来存储max和min,然后基本觉得这样是 可行的,但是一想到需要维护两个heap,作为weekly的第三题,感觉很不应该。 我虽然看到了只需要关注subsequence中的 max 和min,知道顺序不是很重要,只关注subsequence的长度即可,但是离胜利仅仅只有一步之遥。。。
  3. 在开始写代码前,决定还是看下discussion,免得浪费时间走冤枉路,果然discussion没让我失望。我的思路基本是正确的 但是就距离最优最简洁的答案只差一小步,既然我发现顺序不重要,为何不直接把数组排序来做呢,这样问题一下子就变得明了很多。。。 sigh,看来还是差一点火候,这一题差点摧毁我的自信心,不过转念一想,自己刚才没放弃也已经接近完美答案了。 遇到卡壳的时候,关键还是要多发散思维,不要着急一条胡同走到黑,很可能漏掉了什么。

最后实现上有点小问题,在计算2^(j-i)的时候,超时了,然后发现pow(2, (j-i), mod)是一个高效很多的方法,学到了。

pow(2, n, mod)

# 上面比下面这个快很多
2 ** n % mod