Problem

题目链接

Solution

吼题啊吼题！

首先如何求本质不同的子序列个数就是 \(f[val[i]]=1+\sum\limits_{j=1}^k f[j]\)

其中 \(f[i]\) 表示的是以 \(i\) 结尾的子序列个数

先把原数列的不同子序列个数求出来，然后观察一下这个转移，贪心的发现每次都是选一个最早出现的 \(i\) 填到序列末尾，然后更新这个值。

所以填的部分一定是 \(\frac mk\) 个 \(K\) 的排列，还有多出来了 \(m\%k\) 个元素暴力填进去。

每 \(K\) 个元素的转移是一样的，可以拿矩乘做。然后多余的部分求前缀积暴力求就行了。

Code

#include<set>

#include<map>

#include<cmath>

#include<queue>

#include<cctype>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using std::min;

using std::max;

using std::swap;

using std::vector;

const int N=105;

const int M=1e6+5;

typedef double db;

typedef long long ll;

#define int long long

const int mod=1e9+7;

#define pb(A) push_back(A)

#define pii std::pair<int,int>

#define mp(A,B) std::make_pair(A,B)

int n,m,k,per[M];

int val[M];pii las[M];

struct Mat{

    int a[N][N];

    void clear(){

        memset(a,0,sizeof a);

    }

    void init(){

        clear();

        for(int i=1;i<=k+1;i++)

            a[i][i]=1;

    }

    void print(){

        for(int i=1;i<=k+1;i++,puts(""))

            for(int j=1;j<=k+1;j++)

                printf("%lld ",a[i][j]);

    }

    friend Mat operator*(Mat x,Mat y){

        Mat z;z.clear();

        for(int i=1;i<=k+1;i++){

            for(int p=1;p<=k+1;p++){

                for(int j=1;j<=k+1;j++)

                    z.a[i][j]=(z.a[i][j]+x.a[i][p]*y.a[p][j]%mod)%mod;

            }

        } return z;

    }

}cs,f,qzh[N];

int getint(){

    int X=0,w=0;char ch=0;

    while(!isdigit(ch))w|=ch=='-',ch=getchar();

    while( isdigit(ch))X=X*10+ch-48,ch=getchar();

    if(w) return -X;return X;

}

Mat ksm(Mat x,int y){

    Mat ans;ans.init();

    while(y){

        if(y&1) ans=ans*x;

        x=x*x;y>>=1;

    } return ans;

}

signed main(){

    freopen("sequence.in","r",stdin);freopen("sequence.out","w",stdout);

    n=getint(),m=getint(),k=getint();

    int sum=0;f.clear();f.a[1][k+1]=1;

    for(int i=1;i<=k;i++) las[i]=mp(0,i);

    for(int i=1;i<=n;i++){

        val[i]=getint();

        int p=f.a[1][val[i]];

        f.a[1][val[i]]=(sum+1)%mod;

        sum-=p;sum+=f.a[1][val[i]];sum%=mod;

        las[val[i]]=mp(i,val[i]);

    } std::sort(las+1,las+1+k);

    qzh[0].init();

    for(int i=1;i<=k;i++){

        per[i]=las[i].second;

        qzh[i].clear();

        for(int j=1;j<=k+1;j++) qzh[i].a[j][j]=1;

        for(int j=1;j<=k+1;j++) qzh[i].a[j][per[i]]=1;

        qzh[i]=qzh[i-1]*qzh[i];

    } cs=ksm(qzh[k],m/k);

    cs=cs*qzh[m%k];

    f=f*cs;int ans=0;

    for(int i=1;i<=k;i++) (ans+=f.a[1][i])%=mod;

    printf("%lld\n",ans);

    return 0;

}