题解 | 串

不妨令  表示枚举到第  个位置的时候状态为 

• 其中，  状态是当前是否已满足条件——已出现""的子序列
• 而  状态是当前是否已经出现了字母 

发现总共的状态只有  个，记忆化搜索一下即可，每个状态最多只会遍历一次。

ps：我本地  爆栈了，交上去居然过了，非常神奇。

时间复杂度 

#include <bits/stdc++.h>
#pragma GCC optimize(3)
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;

const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
ll dp[N][2][2];
ll dfs(int pos, bool state, bool lead) {
  if(pos == -1) {
    return state;
  }
  if(dp[pos][state][lead] != -1) return dp[pos][state][lead];
  ll ans = 0;
  for(int i = 0; i < 26; i++) {
    char now = i + 'a';
    ans += dfs(pos - 1, state || (lead && now == 's'), lead || now == 'u') % mod;
  }
  return dp[pos][state][lead] = ans;
}

void solve() {
  int n; cin >> n;
  memset(dp, -1, sizeof(dp));
  ll ans = 0;
  for (int i = n; i >= 2; i--) {
      ans += dfs(i - 1, 0, 0);
      ans %= mod;
  }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int T = 1; //cin >> T;
  while(T--) {
    solve();
  }
  return 0;
}