Решение: SPOJ: DSUBSEQ

Question

Мой код дает неправильный ответ на следующий вопрос.Я перепробовал много тестовых случаев, но не смог найти ошибку.

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

# include<bits/stdc++.h>
# define lli long long int
# define pb push_back
# define loop(i,a,b) for(int i=a;i<b;i++)
# define loopl(i,a,b) for(lli i=a;i<b;i++)
# define MAXN 1000
#define INF 1000000000
# define mod 1000000007
using namespace std;

int main()
{
   int t;
   cin>>t;
   while(t--)
   {
     string s;
     cin>>s;
     int n=s.length();
     int visited[26],dp[n+1];
     memset(visited,-1,26);
     loop(i,0,26) visited[i]=-1;
     dp[0]=1;
     loop(i,1,n+1)
     {
            dp[i]=2*dp[i-1];

            if(visited[s[i-1]-'A']!=-1) dp[i]=(dp[i]%mod-dp[visited[s[i-1]-'A']]%mod + mod)%mod ;

            visited[s[i-1]-'A'] = i-1 ;
     }

    cout<<dp[n]<<endl;
   }

}

Примеры тестовых случаев:

ВХОД:

• 3

• AAA

• ABCDEFG

• CODECRAFT

ВЫХОД:

• 4
• 128
• 496

Но я получаю: неправильный ответ# 1

Этот язык - c ++.Я новичок в динамическом программировании.

Answer 1

Входные данные также содержат нижние контрольные примеры.
Будет полезно преобразовать каждый символ в верхний регистр.

Обновление: еще одна вещь, которую вы делаете неправильно, - это не использовать мод в этой строке dp[i]=2*dp[i-1] Представьте себе тест, в котором в этом случае есть четкие 26 букв, и 2 ^ 26 непременно переполнится. Сделайте это dp[i]=(2*dp[i-1])%mod