题解 P2267 【琪琪的项链】

stoorz · 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做了贡献。

所以我们就得到了方程

预处理出对于一个位置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;
}