长度为n的字符串权重之和

· 1 分钟阅读 · 192 字

4.21阿里笔试压轴题，状压dp->快速幂，可惜快速幂写错了，三分之一的测试用例因为超时没通过，复盘一下

题目：一个字符串由小写字母组成，其权重定义为不相邻的元音字母（即aeiou）对的个数，例如“aba”的权重为1，请设计程序，计算长度为n的所有字符串的权重之和，答案取模1000000009。

如n=3时，有权重为1的字符串“aaa”“abe”等，这些字符串的权重和为650。

很容易想到dp，而且想求某一特定字符串的权重并不难，但这并不是本题的重点。

经过比较长时间的思考+动笔计算，确定dp方法：dp[i]表示长为i的所有字符串的权重之和，dp[i]=dp[i-1]*26+(i-2)*25*26^(i-2)；大概的含义为，i-1字符串的权重和，加上第i个字母结尾的元音对所加入的新权重

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

提交，通过66.7%的用例，提示内存过大，于是很容易想到状态压缩：

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

提交，还是只通过66.7%用例，提示超时。

动手算了下，发现可以直接计算dp[i]=sum(i-2)*25*26^(i-2)

快速幂运算：

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

最终时间复杂度O(log n)，空间复杂度O(1)。