自动搬运

查看原文

来自洛谷，原作者为

	stoorz **

搬运于2025-08-24 21:35:46，当前版本为作者最后更新于2019-10-06 22:34:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$$\color{blue}{\texttt{Link:蒟蒻的Blog}}$$

设$f[i]$表示最后一个数字是第$i$个数字的排列个数。

设位置$i$的数字是$a[i]$，那么能对其做成贡献的区间就是$[x,i-1]$，其中$a[x]=a[i]$且$x$尽量大。

因为取任意一个位置$[1,x-1]$的数字，有一下三种选择方法：

• 选择$x$，不选择$i$，那么这个位置就对$x$做了贡献。
• 选择$i$，不选择$x$，这样形成的序列就和上一行所述序列一样，就重复了。
• 选择$x$和$i$，这样依然是对$x$做了贡献。

所以我们就得到了方程

$$f[i]=\sum^{i-1}_{j=x}f[j]\ \ (a[x]=a[i],a[x+1\sim i-1]≠a[i]) $$

预处理出对于一个位置$i$的$last[i]$表示$a[last[i]]=a[i]$且$last[i]$尽量大。然后前缀和维护一下就好了。

时间复杂度$O(n)$

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=500010;
int n,MOD,a[N],b[N],last[N];
ll f[N],sum[N];

int main()
{
	scanf("%d%d",&n,&MOD);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	int tot=unique(b+1,b+1+n)-b-1;
	for (int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,b+1+tot,a[i])-b;  //离散化
	for (int i=1;i<=n;i++)
	{
		if (last[a[i]]) f[i]=(sum[i-1]-sum[last[a[i]]-1])%MOD;
			else f[i]=(sum[i-1]+1)%MOD;  //判断这个颜色是不是第一个出现，如果是，就包含单独这一个颜色的方案，所以+1
		sum[i]=(sum[i-1]+f[i])%MOD;
		last[a[i]]=i;
	}
	printf("%lld",(sum[n]%MOD+MOD)%MOD);
	return 0;
}