oj.uz

Submission #805735

# Submission time Handle Problem Language Result Execution time Memory
805735 2023-08-03T22:13:28 Z Sputnik123 Binary Subsequences (info1cup17_binary) C++14
0 / 100
 6 ms 308 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 300 KB Output isn't correct
2 Halted 0 ms 0 KB -