可做场，拜谢fengwu老师。

A. Reversi (AGC031B)

~~一眼切了~~
设 $ dp_i $ 表示考虑到第 $ i$ 个石头的总方案数。
可由两种情况转移，不选择染色和选择染色，不染色直接由 $ dp_{i-1} $ 转移过来，染色由上一个和当前颜色相同的的石头转移过来，相当于把两个石子之间的染色。因为一个石子被染色后就不可以在给别的石子染色。
设 $ h_i $表示和当前石子颜色相同的最近的石子的位置。
则：

\[dp_i=dp_{i-1} + dp_{i-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;
}

JZTXT

CSP模拟26

A. Reversi (AGC031B)