Submission #805735

#	Time	Username	Problem	Language	Result	Execution time	Memory
805735		Sputnik123	Binary Subsequences (info1cup17_binary)	C++14	0 / 100	6 ms	308 KiB

binary

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000000007;

int countDistinctSubsequences(string s) {
    int n = s.length();
    vector<int> dp(n + 1, 0);
    vector<int> lastOccur(256, -1);
    dp[0] = 1;

    for (int i = 1; i <= n; i++) {
        dp[i] = (2 * dp[i - 1]) % MOD;
        if (lastOccur[s[i - 1]] != -1) {
            dp[i] = (dp[i] - dp[lastOccur[s[i - 1]] - 1] + MOD) % MOD;
        }
        lastOccur[s[i - 1]] = i;
    }

    return dp[n];
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        int K;
        cin >> K;
        int distinctSubsequences = countDistinctSubsequences("101");
        cout << distinctSubsequences % MOD << endl;
        cout << "1" << endl;
    }

    return 0;
}

• Subtask 1: 0 / 43
• Subtask 2: 0 / 39
• Subtask 3: 0 / 18