luogu P2267 琪琪的项链

---恢复内容开始---

神仙题。。。

第一眼还以为是道数学题。。。

看了题解发现是道恶心的Dp。。

设 f[i] 表示 以珠子 i 为结尾的方案数（必须选i），然后能对其做出贡献的只有  x ~ i-1 这段区间。。

x表示 a [ x ] == a [ i ] && a[ x+1 ~  i-1 ] != a [ i ] 也就是最后一个和 i 颜色相同的位置。。

为什么？？

因为在1~x-1中选出若干个后，再选 x 或 i 的话就重复了。。

所以转移方程就是

f[i]=(sigma)(j=x,j<=i-1)f[j] (a[x]==a[i] ,a[x+1  ~  i - 1]!=a[i] )

额就是这样子。。

对于我这种蒟蒻太难了 。。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
#define N 500010
using namespace std;
int n,m,last[N],tmp[N];
ll a[N],b[N],sum[N];
inline ll read(){
	char c=getchar();ll x=0,flag=1;
	while(c<'0' || c>'9'){if(c=='-') flag=-1;c=getchar();}
	while(c>='0' && c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar();
	return x*flag;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++) a[i]=read(),b[i]=a[i];
	sort(b+1,b+n+1);int cnt=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
	for(int i=1;i<=n;i++){last[i]=tmp[a[i]];tmp[a[i]]=i;}
	for(int i=1;i<=n;i++){
		if(last[i]) sum[i]=(2*sum[i-1]%m-sum[last[i]-1])%m;
		else sum[i]=(sum[i-1]+sum[i-1]+1)%m;
	} 
	printf("%lld
",(sum[n]%m+m)%m);return 0;
}