长度为n的字符串权重之和
JRQZ
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)。