This was the final problem in an Alibaba online assessment on April 21st. The intended solution was state-compressed DP → fast exponentiation. Unfortunately, I made an error in the fast exponentiation implementation, causing one-third of the test cases to fail due to TLE. Here’s a post-mortem analysis.

Problem: A string consists of lowercase letters. Its weight is defined as the number of non-adjacent vowel pairs (vowels: a, e, i, o, u). For example, the weight of “aba” is 1. Design a program to calculate the total weight of all strings of length n, with the answer taken modulo 1000000009.

For n = 3, strings with weight 1 include “aaa”, “abe”, etc. The total weight of all such strings is 650.

DP is an intuitive approach, and computing the weight of any given string is straightforward — but that is not the core challenge here.

After extended analysis and manual calculation, the DP recurrence was determined: dp[i] represents the total weight of all strings of length i.

dp[i] = dp[i-1] * 26 + (i-2) * 25 * 26^(i-2)

The rough interpretation: the weight carried over from strings of length i-1 (scaled by 26 new possible last characters), plus the new vowel pairs introduced by the i-th character being a vowel.

#include <bits/stdc++.h>

#define MOD 1000000009
using namespace std;

long solve(int n);

int main() {
    int n;
    cin>>n;
    cout<<solve(n)<<endl;
}

long solve(int n) {
    vector<long> dp(n+1, 0);
    long pow=1;
    for(int i=3; i<=n; ++i) {
        pow = pow*26%MOD;
        dp[i] = (dp[i-1]*26%MOD + (i-2)*25*pow%MOD*26%MOD)%26;
    }
    return dp[n];
}

Submitted — 66.7% of test cases passed. Memory usage was too high, so state compression was applied:

#include <bits/stdc++.h>

#define MOD 1000000009
using namespace std;

long solve(int n);

int main() {
    int n;
    cin>>n;
    cout<<solve(n)<<endl;
}

long solve(int n) {
    long pre=0, cur;
    long pow=1;
    for(int i=3; i<=n; ++i) {
        pow = pow*26%MOD;
        cur = (pre * 26 % MOD + ((i-2) * 25 % MOD) * pow % MOD) % MOD;
        pre = cur;
    }
    return cur;;
}

Still only 66.7% passed — TLE this time.

After working it out by hand, a direct closed-form formula was found:

dp[i] = sum(i-2) * 25 * 26^(i-2)

Fast exponentiation:

#include <bits/stdc++.h>

#define MOD 1000000009
using namespace std;

long solve(int n);

long sum(int n);

long quickPow(int a, int b);

int main() {
    int n;
    cin>>n;
    cout<<solve(n)<<endl;
}

long solve(int n) {
    if(n<=2) return 0;
    return sum(n-2)*25%MOD*quickPow(26, n-2)%MOD;
}

long sum(int n) {
    return (1+n)*n/2%MOD;
}

long quickPow(int a, int b) {
    long base = a, ans = 1;
    while(b) {
        if(b%2) ans = ans*base%MOD;
        base = base*base%MOD;
        b /= 2;
    }
    return ans;
}

Final time complexity: O(log n). Space complexity: O(1).