The Sum of Legal Set

https://blog.csdn.net/qq_46105170/article/details/110621205

【Leetcode】50. Pow(x, n)_50. pow(x, n) 分治-CSDN博客

给定一个长n nn的数组A AA和一个整数k kk，问A AA有多少个子集使得其最大最小值之和是小于等于k kk的。答案模1 0 9 + 7 10^9+710 9 +7后返回。空子集不算。

先对A AA排序，接着用对撞双指针，枚举最小最大值。设指针i ≤ j i\le ji≤j，如果A [ i ] + A [ j ] ≤ k A[i]+A[j]\le kA[i]+A[j]≤k，说明以A [ i ] A[i]A[i]为最小值，A [ i : j ] A[i:j]A[i:j]为最大值的子集都是满足条件的，这样的子集的个数就是2 j − i 2^{j-i}2 j−i 个，计算完这样的子集之后，将i ii右移；否则如果A [ i ] + A [ j ] > k A[i]+A[j]> kA[i]+A[j]>k，则左移j jj。至于求2 k 2^k2 k ，可以用快速幂来做，时间复杂度可以降到O ( log ⁡ k ) O(\log k)O(logk)，具体参考https://blog.csdn.net/qq_46105170/article/details/104338070。代码如下： ————————————————

原文链接：https://blog.csdn.net/qq_46105170/article/details/110621205

import java.util.Arrays;

public class Solution {
    /**
     * @param a: the array
     * @param k: the target
     * @return: the sum of the legal set
     */
    public int theSumofLegalSet(int[] a, int k) {
        // Write your code here.
        Arrays.sort(a);
        
        long res = 0, MOD = (long) (1E9 + 7);
        for (int i = 0, j = a.length - 1; i <= j; ) {
            if (a[i] + a[j] <= k) {
                res += pow2(j - i, MOD);
                res %= MOD;
                i++;
            } else {
                j--;
            }
        }
        
        return (int) res;
    }
    
    private long pow2(int n, long MOD) {
        long res = 1, p = 2;
        while (n > 0) {
            if ((n & 1) == 1) {
                res *= p;
                res %= MOD;
            }
            
            p *= p;
            p %= MOD;
            
            n >>= 1;
        }
        
        return res;
    }
}

pow(x,n)

算x n x^nx n 。

思路是快速幂（exponentiating by squaring）。主要思路是对n nn做二进制展开，然后对这些二进制位从右向左扫描，用一个变量来保存到当前这个二进制位，x xx的那么多次次方的结果是多少。

设r rr是答案。举个例子来说，如果要算x 13 x^{13}x 13 ，由于13 = ( 1101 ) 2 13=(1101)_213=(1101) 2 ​ ，x xx首先保存的是x 2 0 x^{2^0}x 2 0

是多少，也就是x 1 x^1x 1 ，那其实就是x xx。接着开始从右向左扫描1101 11011101，扫描到第0 00位时遇到1 11，就给r rr乘上x 2 0 x^{2^0}x 2 0

，同时x xx需要平方一下，这样就保存了x 2 1 x^{2^1}x 2 1

这个值，扫描到第1 11位时遇到0 00，r rr保持原样，而x xx继续平方一下，得到了x 2 2 x^{2^2}x 2 2

，继续扫描到1 11，这时r rr乘一下x 2 2 x^{2^2}x 2 2

，如此下去r rr又乘了x 2 3 x^{2^3}x 2 3

，扫描结束。我们统计一下会发现，r = x 2 0 × x 2 2 × x 2 3 = x 2 0 + 2 2 + 2 3 = x 13 r=x^{2^0}\times x^{2^2}\times x^{2^3}=x^{2^0+2^2+2^3}=x^{13}r=x 2 0

×x 2 2

×x 2 3

=x 2 0 +2 2 +2 3

=x 13 ，正好是所求结果。代码如下： ————————————————

原文链接：https://blog.csdn.net/qq_46105170/article/details/104338070

class Solution {
 public:
  double myPow(double x, int m) {
    double res = 1.0;
    long long n = m;
    if (n < 0) x = 1.0 / x;
    n = abs(n);
    while (n) {
      if (n & 1) res *= x;
      x *= x;
      n >>= 1;
    }
    return res;
  }
};