可做场，拜谢fengwu老师。
A. Reversi (AGC031B)
一眼切了
设 $ dp_i $ 表示考虑到第 $ i$ 个石头的总方案数。
可由两种情况转移，不选择染色和选择染色，不染色直接由 $ dp_{i-1} $ 转移过来 ，染色由上一个和当前颜色相同的的石头转移过来，相当于把两个石子之间的染色。因为一个石子被染色后就不可以在给别的石子染色。
设 $ h_i $表示和当前石子颜色相同的最近的石子的位置。
则：
复杂度为 $ O(n) $
点击查看代码
#include <iostream>
#include <cstdio>
#include <vector>
#define int long long
const int MAXN=5e6+10;
const int mod=1e9+7;
using namespace std;
inline int read() {
int f=1,x=0;
char ch=getchar();
while(ch>'9' || ch<'0') {
if(ch=='-') {
f=-1;
}
ch=getchar();
}
while(ch>='0' && ch<='9') {
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return f*x;
}
int n;
int a[MAXN];
int cnt[MAXN], beh[MAXN];
int dp[MAXN];
signed main() {
n=read();
for(int i=1;i<=n;i++) {
a[i]=read();
beh[i]=cnt[a[i]];
cnt[a[i]]=i;
}
dp[0]=0, dp[1]=1;
for(int i=2;i<=n;i++) {
dp[i]=dp[i-1]%mod;
if(beh[i]+1==i) continue;
dp[i]=(dp[i]+dp[beh[i]])%mod;
}
printf("%lld",dp[n]%mod);
return 0;
}