正題

題目大意

給出一個長度為\(n\)的字元串\(a\)，求它的所有子序列的本質不同子序列個數。

\(1\leq n\leq 10^6\)

解題思路

考慮每個子序列産生的貢獻，為了防止算重我們一個隻統計走子序列自動機上的邊的子序列，也就是說對于\(T\)對\(S\)産生貢獻當且僅當\(T\)中沒有任何一個字元能在\(S\)上比對到更前的位置。

設\(f_i\)表示以位置\(i\)結尾的子序列産生的貢獻和，\(g_i\)表示目前以字元\(i\)結尾的貢獻和是多少。

那麼每次\(f\)直接用\(g\)來做，然後再用\(f\)更新\(g\)，具體地如果下一個字元和這個字元不能那麼可以選擇也可以不選擇是以\(g_j\)需要乘二，否則不乘就好了。

時間複雜度：\(O(26n)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1e6+10,P=1e9+7;
ll n,ans,g[26],pw[N];
char s[N];
signed main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=0;i<26;i++)g[i]=1;
	pw[0]=1;for(ll i=1;i<=n;i++)pw[i]=pw[i-1]*2%P;
	for(ll i=1;i<=n;i++){
		ll c=s[i]-'a',f=g[c];
		ans=(ans+f*pw[n-i])%P;
		for(ll j=0;j<26;j++){
			if(j==c)g[j]=(g[j]+f)%P;
			else g[j]=(g[j]*2ll+f)%P;
		}
	}
	printf("%lld\n",ans);
	return 0;
}