F题题解

令f【i】（1<=i<=k)表示以i结尾的不同子序列的个数，则f[i]=1+f[j] (1<=j<=k)(在每一个数的后面加上一个i，再加上本身的i作为一个子序列）
显然每次的以i结尾的字符列变成了最大值，对于后面的m个数，我们会将本次最小的f【i】变成最大，也就是我们会在当前位填上i，这样才会保证子序列个数最大。
表达式可以递推，如果我们这样构造（1，f[1]...f[k])，则转移矩阵为 k+1阶矩阵
每次会消除f[1]，因此我们要对f进行排序，（注意我们要在取模意义下排序）

const int sz=109;
struct mat {
  ll a[sz][sz];
  inline mat() { memset(a, 0, sizeof a); }
  inline mat operator*(const mat& T) const {
    mat res;
    int r;
    for (int i = 0; i < sz; ++i)
      for (int k = 0; k < sz; ++k) {
        r = a[i][k];
        for (int j = 0; j < sz; ++j)
          res.a[i][j] += T.a[k][j] * r, res.a[i][j] %= MOD;
      }
    return res;
  }
  inline mat operator^(ll x) const {
    mat res, bas;
    for (int i = 0; i < sz; ++i) res.a[i][i] = 1;
    for (int i = 0; i < sz; ++i)
      for (int j = 0; j < sz; ++j) bas.a[i][j] = a[i][j] % MOD;
    while (x) {
      if (x & 1) res = res * bas;
      bas = bas * bas;
      x >>= 1;
    }
    return res;
  }
};
ll d[109];
struct node
{
    ll v,id;
}f[109];
bool cmp(node A,node B)
{
    return A.id<B.id;
}
int main()
{
    ll n,m,k;
    while(scanf("%lld%lld%lld",&n,&m,&k)!=EOF)
    {
        ll sum=0;
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            ll tm=f[x].v;
            f[x].v=sum+1;

            f[x].v%=MOD;
            sum=(sum-tm+MOD)%MOD;
            sum=(sum+f[x].v)%MOD;
            f[x].id=i;
        }    
        f[0].v=1;
        sort(f+1,f+1+k,cmp);
        mat ans;
        for(int i=0;i<=k;i++)
        {
            ans.a[i][k]=1;
        }
        ans.a[0][0]=1;
        for(int i=2;i<=k;i++)
        {
            ans.a[i][i-1]=1;
        }
        ans=ans^(m+1);
        ll res=0;
        for(int i=0;i<=k;i++)
        {
            res+=ans.a[i][k]*f[i].v;
            res%=MOD;
        }
        res--;
        res=(res+MOD)%MOD;
        printf("%lld\n",res);
    }
}