008.md

008 - AtCounter (★4)

解答

#include <iostream>
#include <string>
#include <array>
#include <vector>

int main()
{
	constexpr int MOD = 1'000'000'007;
	const std::string atcoder = "atcoder";

	// N 文字
	int N;
	std::cin >> N;

	std::string S;
	std::cin >> S;

	std::vector<std::array<int, 8>> dp(N + 1);
	dp[0][0] = 1;

	for (int i = 0; i < N; ++i)
	{
		const char ch = S[i];

		for (int k = 0; k <= 7; ++k)
		{
			dp[i + 1][k] += dp[i][k];

			if (ch == atcoder[k])
			{
				dp[i + 1][k + 1] += dp[i][k];
			}

			dp[i + 1][k] %= MOD;
		}
	}

	// 解答を出力
	std::cout << dp.back().back() << '\n';
}