Counting Subsets

Characters and SNPs

A character is any feature (genetic, physical, etc.) that divides a collection of organisms into two separate groups. One commonly used genetic character is the possession of a single-nucleotide polymorphism, or SNP.
In a process called genotyping, the SNP markers taken from a large number of human donors have been used very successfully to catalogue the migration and differentiation of human populations over the last 200,000 years. For $199, you can participate in National Geographic‘s Genographic Project, and discover your own genetic heritage.
Whether we use genetic or physical characters, we may think of a collection of nn characters as a collection of “ON”/“OFF” switches. An organism is said to possess a character in the “ON” position (although often the assignment of “ON”/“OFF” is arbitrary). Given a collection of taxa, we may represent a character by the collection of taxa possessing the character.

Problem

A set is the mathematical term for a loose collection of objects, called elements. Examples of sets include {the moon, the sun, Wilford Brimley} and R, the set containing all real numbers. We even have the empty set, represented by ∅∅ or {}{}, which contains no elements at all. Two sets are equal when they contain the same elements. In other words, in contrast to permutations, the ordering of the elements of a set is unimportant (e.g., {the moon, the sun, Wilford Brimley} is equivalent to {Wilford Brimley, the moon, the sun}). Sets are not allowed to contain duplicate elements, so that {Wilford Brimley, the sun, the sun}{Wilford Brimley, the sun, the sun} is not a set. We have already used sets of 2 elements to represent edges from a graph.
A set A is a subset of BB if every element of AA is also an element of B, and we write A⊆B. For example, {the sun, the moon}⊆{the sun, the moon, Wilford Brimley}, and ∅ is a subset of every set (including itself!).
As illustrated in the biological introduction, we can use subsets to represent the collection of taxa possessing a character. However, the number of applications is endless; for example, an event in probability can now be defined as a subset of the set containing all possible outcomes.
Our first question is to count the total number of possible subsets of a given set.
Given: A positive integer nn (n≤1000).
Return: The total number of subsets of {1,2,…,n} modulo 1,000,000.

Sample Dataset

3

Sample Output

8

Hint

What does counting subsets have to do with characters and “ON”/“OFF” switches?

Solution

前面题目说过，使用二进制 01 表示枚举子集。因此最终共有 个，本题的关键难点在于 和取模。也就是本题考点快速幂和取模定理。
取模运算的等价变形适合加法、减法、乘法

但是，取模运算的等价变形不符合除法

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
    int countSubsets(int n) {
        // 使用二进制快速幂计算 pow(2, n, modulus) 结果
        // base 必须是 long long, 999999 * 999999 会导致 int 溢出
        unsigned long long base = 2, modulus = 1'000'000;  
        int ret = 1;
        while (n) {
            if (n & 1) {
                ret = (ret * base) % modulus;
            }
            // n 右移一位，删除低位
            n >>= 1;
            base = (base * base) % modulus;  // 取模
        }
        return ret;
    }
};
int main() {
    int n;
    cin >> n;
    cout << Solution().countSubsets(n) << endl;
    return 0;
}

而 python 中的 pow 第三个参数非常有用！

pow(x, y, z=None, /)
    Equivalent to x**y (with two arguments) or x**y % z (with three arguments)
    Some types, such as ints, are able to use a more efficient algorithm when
    invoked using the three argument form.