Submission #1186456

---

Source Code Expand

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <map>
#include <set>
#include <array>
#include <queue>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>
#include <functional>
#define MOD 1000000007
#define INF 11234567890
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;
typedef std::pair<int, int> P;

int N, M, f[112345];
LL memo[112345];

LL m(int s)
{
	int res = 0;
	if (memo[s] != -1) { return memo[s]; }
	if (s >= N)
	{
		return memo[s] = 1;
	}
	int seek = 1;
	std::map<int, bool>list;
	list[f[(s - 1)]] = true;
	while ((s - 1) + seek < N)
	{
		if (list[f[(s - 1) + seek]] == false)
		{
			list[f[(s - 1) + seek]] = true;
			res += (m(s + seek + 1) % MOD);
			res %= MOD;
		}
		else
		{
			break;
		}
		++seek;
	}
	res += (m(s + 1) % MOD);
	res %= MOD;
	return memo[s] = (res % MOD);
}

int main()
{
	in >> N >> M;
	rep(i, N) { in >> f[i]; }

	memset(memo, -1, sizeof(memo));

	out << m(1) % MOD << std::endl;
	return 0;
}

Submission Info

Judge Result