Spoj DSUBSEQ – CPP solution

Problem: http://www.spoj.com/problems/DSUBSEQ/

Say that so far you have generated so far N strings totally without using the letter A. Then you append the letter A and you generate N+N strings. Later, when you add the letter A again, you would like to know how many strings have been generated using the letter A. Obviously, if you add the letter A to those strings, you won’t get distinct.
Keep the number of totally string generated so far and the number of strings generated by using some letter. Later, when adding some letter (say K), then the strings you would generate is (TOTAL – NUM OF STRINGS GENERATED USING K).
Just update the invariant correctly.

#include <cstdio>

typedef long long ll;
#define MOD 1000000007LL
ll arr[30];
char str[100001];

inline ll mod(ll num) {
    num %= MOD;
    if (num < 0LL) num += MOD;
    return num;

int main() {
    int t;
    while (t--) {
        scanf("%s", str);
        int i = 0;
        ll sum = 1LL;
        while (str[i]) {
            ll tmp = mod(sum-arr[str[i]-'A']);
            arr[str[i]-'A'] = mod(arr[str[i]-'A']+tmp);
            sum = mod(sum+tmp);
        //sum = mod(sum+1LL);
        for (int i = 0; i < 30; i++) arr[i] = 0LL;
        printf("%lldn", sum);
    return 0;

Leave a Reply

Your email address will not be published. Required fields are marked *