京东笔试8-27号 最后一题（漂亮数）
输入一个n
输出长度为n的，只包括小写字母的，至少有两个red的字符串的数量。
解决方案：用总的字符串数量 减去 不包括一个red的，再减去包括一个red的字符串的数量
dp[i][j]表示前i个字符，其中第i个字符已经匹配到red的第j位了的字符串个数，例如dp[6][2]表示前6个字符，最后已经匹配到re了的字符串个数，即以re结尾的字符串个数。
代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
ll dp[N][4];
void init(int n){
dp[0][0] = 1;
for(int i = 1; i <= n; i ++){
dp[i][0] = (dp[i - 1][0] * 25 % mod + dp[i - 1][1] * 24 % mod + dp[i - 1][2] * 24 % mod) % mod;
dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod;
dp[i][2] = dp[i - 1][1];
}
}
int main()
{
int n;
cin >> n;
ll ans = 1;
for(int i = 1; i <= n; i ++){
ans = ans * 26 % mod;
}
init(n);
ans = (ans - (dp[n][0] + dp[n][1] + dp[n][2]) % mod + mod) % mod;
for(int i = 1; i <= n - 2; i ++){
ll left = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod;
ll right = (dp[n - i - 2][0] + dp[n - i - 2][1] + dp[n - i - 2][2]) % mod;
ans = (ans - left * right % mod + mod) % mod;
}
cout << ans << endl;
return 0;
} 
查看24道真题和解析
