百度之星第三场 - BD202317 石碑文

Solost

2023 年 10 月 05 日

197 次浏览

暂无评论

1746字数

题目题解

## 题目链接

[题目链接](https://www.matiji.net/exam/brushquestion/17/4347/179CE77A7B772D15A8C00DD8198AAC74)

## 题目大意

给你一个长度为n的字符串，问你有多少个连续shs三个及三个以上的字符串种类

## 题解

状态压缩dp

dp状态为dp[i,j]含义为第i个字符，凑了j个shsshsshs的第几个字符

结尾为s的时候，可以加s凑成s结尾，加h凑成sh,随便加凑成空集

结尾为sh，加s可以凑成一个空集，并且数量加一，随便加凑成空集

已经满3个以后随便加，都不会影响答案

## 代码

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define fp(i, a, b) for (int i = a, i##_ = b; i <= i##_; ++i)
#define fd(i, a, b) for (int i = a, i##_ = b; i >= i##_; --i)

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
using pii = pair<int, int>;
using ull = unsigned long long;

const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const int N = 2e6 + 10;
ll f[N][20];
void solve() {
    int n;
    cin >> n;
    f[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 10; j++) {
            if (j == 9)
                f[i + 1][j] = (f[i + 1][j] + 26 * f[i][j]) % mod;//已经满3个
            else if (j % 3 == 1) {
                f[i + 1][j] = (f[i + 1][j] + f[i][j]) % mod;//s加了自己
                f[i + 1][j + 1] = (f[i + 1][j + 1] + f[i][j]) % mod;//加了h
                f[i + 1][j - 1] = (f[i + 1][j - 1] + 24 * f[i][j]) % mod;//随便加
            } else {
                f[i + 1][j + 1] = (f[i + 1][j + 1] + f[i][j]) % mod;//sh加了s
                f[i + 1][j / 3 * 3] = (f[i + 1][j / 3 * 3] + 25 * f[i][j]) % mod;//sh加了任意字符
            }
        }
    }
    cout << f[n][9] << '\n';
}

int main() {
    IOS;
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 10 月 05 日