1 条题解

  • 0
    @ 2021-11-7 20:57:21

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

    #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; }

    • 1

    信息

    ID
    209
    时间
    2000ms
    内存
    512MiB
    难度
    7
    标签
    (无)
    递交数
    36
    已通过
    10
    上传者