Description

Submission

class Solution {
    typedef long long ll;
public:
    int countSpecialSubsequences(vector<int>& nums) {
        const int M = 1e9 + 7;
        vector<ll> dp(3, 0);

        dp[0] = 1;

        for(auto x: nums) {
            if(x == 0) {
                dp[0] = (dp[0] * 2) % M;
            } else if(x == 1) {
                dp[1] = (dp[0] - 1 + dp[1] * 2) % M;        // dp[0] - 1: remove the empty set
            } else if(x == 2) {
                dp[2] = (dp[1] + dp[2] * 2) % M;
            }
        }

        return dp[2];
    }
};

// corresponding sequences
// dp[0]: 0
// dp[1]: 01
// dp[2]: 012