总觉得就我一个人没有把问题转换成贡献

#include

#include

#include

#include

#include

#include

using namespace std;

const long long mod = 1000000007;

inline int read() {

register int x = 0, f = 1; register char ch = getchar();

while(ch < '0' || ch > '9'){if(ch == '-')f = -1; ch getchar();}

while(ch >= '0' && ch <= '9'){x = x * 10 + ch - 48; ch = getchar();}

return x * f;

}

templateinline T mmin(register T x, register T y) {

return x > y ? y : x;

} templateinline T mmax(register T x, register T y) { return x > y ? x : y; } int n; long long dp[1000007]; int lst[37], cnt[37]; long long del[37]; char ch[1000007]; inline long long power(long long a, long long b) { long long ret = 1ll; for(; b; b >>= 1) { if(b & 1) ret = ret * a % mod; a = a * a % mod; } return ret; } signed main() { scanf("%s", ch + 1); n = strlen(ch + 1); dp[1] = 1; cnt[ch[1] - 'a'] = 1; for(int i = 2; i <= n; ++i) { int x = ch[i] - 'a'; dp[i] = dp[i - 1] * 3 % mod; dp[i] = (dp[i] - del[x] % mod + mod) % mod; dp[i] = (dp[i] + power(2, i - cnt[x] - 1)) % mod; //这里的快速幂是可以避免的，但是这样写方便点（反正不会T for(int j = 0; j < 26; ++j) if(j != x) del[j] = del[j] * 2 % mod; del[x] = (del[x] + dp[i - 1]) % mod; ++cnt[x]; } printf("%lld\n", dp[n]); return 0; }