提出 #319908

---

ソースコード 拡げる

#include <iostream>
#include <stdio.h>
#include <set>
#include <map>
#include <list>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits.h>
#include <string>
#include <queue>
#include <functional>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <string.h>
using namespace std;

namespace{
	#define		CAST( T, val )		( (T)( val ) )
	#define		CASE( lb )			break; case lb:
	#define		CASE_CONTINUE( lb )	case lb:
	#define		CASE_DEFAULT		break; default:
	#define		For( i, s )			for(int i= 0; i< (int)s; i++)
	#define		ForA( i, a, s )		for(int i= (int)a; i< (int)s; i++)
	#define		ForSize( i, s )		for(int i= 0, size= (int)s; i< size; i++)
	#define		ForSizeA( i, a, s )	for(int i= (int)a, size= (int)s; i< size; i++)
	#define		ForItr( itr, con )	for(auto itr= con.begin(); itr!= con.end(); itr++)
	#define		ForStr( i, str )	for(int i= 0; str[i]; i++)
	#define		GOTO( lb )			goto lb
	#define		LABEL( lb )			lb:

	typedef		long long		LLint;
	typedef		unsigned int	Uint;
	typedef		unsigned char	Uchar;
	typedef		unsigned short	Ushort;

	const double EPS= 0.00000000023283064365386962890625;	//	2^-32
	template <typename T> class priority_queue_less : public priority_queue<T,vector<T>,greater<T> >{};
}
//	合同式
namespace{
	class Mod{
		typedef		int		Type;
	public:
		static const Type N= 1000000007;
		Type x;
		
		//	opr, cst
		Mod operator +(const Mod& m) const{ return Mod(x+m.x); }
		const Mod& operator +=(const Mod& m){ x= (x+m.x)%N; return *this; }
		Mod operator -(const Mod& m) const{ return Mod(x-m.x); }
		const Mod& operator -=(const Mod& m){ x= (x-m.x)%N; return *this; }
		Mod operator *(const Mod& m) const{ return Mod(x*m.x); }
		const Mod& operator *=(const Mod& m){ x= (x*m.x)%N; return *this; }
		Mod operator /(const Mod& m) const{
			//	フェルマーの小定理より, m.x の逆元は m.x^( HOU-2 )
			const Type n= N-2; Type p= m.x, r= x; for(Type b= 1; b< n; b<<= 1){ if( n & b ) r= r*p%N; p= p*p%N; } return r;
		}
		const Mod& operator /=(const Mod& m){ return *this= *this /m; }
		Mod(){}
		Mod(const Type x) : x(x%N){}
	};
	istream& operator >>(istream& in, Mod& p){
		return in>> p.x;
	}
	ostream& operator <<(ostream& out, const Mod& p){
		return out<< p.x;
	}
}

const int Ten5= 100000;
int FMem[Ten5];
Mod DP[Ten5];

int main(){
	int N, M;
	cin>> N>> M;

	int *F= FMem;
	For( i, N ){ cin>> F[i]; F[i]--; }

	Mod* dp= DP;
	set<int> set;
	dp[0]= 1;
	ForA( n, 1, N ){
		set.clear();
		set.insert( F[n] );

		for(int i= n-1;; i--){
			if( i == -1 ){
				dp[n]+= 1;
				break;
			}else{
				dp[n]+= dp[i];
				if( set.find( F[i] )!= set.end() ) break;
				set.insert( F[i] );
			}
		}
	}

	cout<< dp[N-1]<< endl;
	
	return 0;
}

提出情報

ジャッジ結果