规定长度的上升子序列的个数

给定一个长度为n的序列(n <= 100) ，给定m(m <= n),求该序列中有多少值不相同的长度为m的严格上升子序列。

原始数据储存在数组a[]里面，用dp[i][j]表示以i为结尾的长度为j的上升子序列的个数，在满足a[k]<a[i]的情况下，dp[i][j] += dp[k][j-1]，需要注意的是中间要取模。

因为要求值不同，所以a:1 2 2 4 时，a[1] a[2] a[4]与a[1] a[3] a[4]是相同情况（设下标从1开始），所以用一个 vis[] 数组标记这个数是否用过。

#include<iostream>
#include<cstring>
#define maxn 105
#define mod 1000000007
using namespace std;

int dp[maxn][maxn];
int num[maxn];
int vis[maxn];

int main()
{
    int T;

    cin>>T;
    while (T > 0)
    {
        T--;

        int n, m, x;
        cin>>n>>m;
        int last = -1;
        int tot = 0;
        memset(dp,0,sizeof(dp));
        memset(vis,0,sizeof(vis));  //标记值是否用过
        for (int i=1; i<=n; i++)
        {
            cin>>num[i];
            dp[i][1] = 1;
        }

        for (int i=2; i<=n; i++)
            for (int j=1; j<=n; j++)
        {
            for (int k=i-1; k>=1; k--)
                if (num[i] > num[k] && !vis[num[k]])
            {
                vis[num[k]] = 1;
                dp[i][j] += dp[k][j-1];
                dp[i][j] %= mod;
            }
            memset(vis,0,sizeof(vis));
        }

        memset(vis,0,sizeof(vis));
        int ans = 0;
        for (int i=n; i>=1; i--)
        {
            if (vis[num[i]])
                continue;
            vis[num[i]] = 1;
            ans += dp[i][m];
            ans %= mod;
        }

        cout<<ans<<endl;
    }

    return 0;
}