这个题是计算不同子序列的和；
spoj上的那个同名的题是计算不同子序列的个数；
其实都差不多；
计算不同子序列的个数使用dp的思想；
从头往后扫一遍
如果当前的元素在以前没有出现过，那么dp[i]=dp[i-1]*2+1;
不然找到最右边的这个元素出现的位置j；
dp[i]=d[i]*2-dp[j];
spoj代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 1000000007
using namespace std; char s[];
int pos[];
int biao[];
int dp[]; int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
memset(biao,,sizeof biao);
scanf("%s",s+);
n=strlen(s+);
for(int i=; i<=n; i++)
{
pos[i]=biao[s[i]-'A'];
biao[s[i]-'A']=i;
}
dp[]=;
for(int i=; i<=n; i++)
{
if(pos[i]==)
{
dp[i]=(dp[i-]*+);
while(dp[i]>=mod)dp[i]-=mod;
}
else
{
dp[i]=(dp[i-]*-dp[pos[i]-]);
if(dp[i]<)dp[i]+=mod;
while(dp[i]>=mod)dp[i]-=mod;
}
}
printf("%d\n",dp[n]+);
}
return ;
}
csuoj代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 1000000007
using namespace std; char s[];
int pos[];
int biao[];
int dp[];
long long sum[]; int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
memset(biao,,sizeof biao);
scanf("%s",s+);
n=strlen(s+);
for(int i=; i<=n; i++)
{
pos[i]=biao[s[i]-''];
biao[s[i]-'']=i;
}
dp[]=;
for(int i=; i<=n; i++)
{
long long tmp=sum[i-];
if(pos[i]==)
{
dp[i]=dp[i-]*;
if((s[i]-'')>)dp[i]+=;
while(dp[i]>=mod)dp[i]-=mod;
}
else
{
dp[i]=(dp[i-]*-dp[pos[i]-]);
tmp-=sum[pos[i]-];
if(tmp<)tmp+=mod;
if(dp[i]<)dp[i]+=mod;
while(dp[i]>=mod)dp[i]-=mod;
}
sum[i]=(tmp*+(long long)(dp[i]-dp[i-])*(s[i]-'')+sum[i-])%mod;
if(sum[i]<=)sum[i]+=mod;
}
printf("%lld\n",sum[n]);
}
return ;
}