Submission #1185835

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cassert>
#include<map>
#include<climits>
#include<cstdlib>
#include<cstring>

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;
const ll mod = 1000000007LL;

int N,M,f[100100];
int tmp[100100];

void compute() {
  memset(tmp,-1,sizeof tmp);
  vector<int> pre(N+1,-1);
  rep(i,N) {
    pre[i] = tmp[f[i]];
    tmp[f[i]] = i;
  }
  vector<ll> dp(N+1,0);
  dp[0] = 1;
  REP(i,1,N) { 
    dp[i] = dp[i-1]; 
    if( f[i] == f[i-1] ) continue;
    int p = pre[i];
    if(p == -1) ( dp[i] += dp[i-1] ) %= mod;
    else        ( dp[i] += dp[i-1] - ( dp[p+1] - dp[p] ) ) %= mod;
  }
  cout << dp[N-1] << endl;
}

int main() {
  cin >> N >> M;
  rep(i,N) { cin >> f[i]; --f[i]; }
  compute();
  return 0;
}

Submission Info

Judge Result