51nod 1202 子序列个数

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1202
dp[i] $dp\left[i\right]$表示计算到第 i $i$个的子序列个数
①：如果第 i $i$个这个数 x $x$是没出现过的，那么所有的子序列就是：原来 i−1 $i-1$的所有子序列 + $+$把所有原来 i−1 $i-1$的子序列的最后一位换成 x $x$，再 +x $+x$这个数单独作为一个子序列
那么转移方程就是
dp[i]=dp[i]+dp[i]+1 $dp\left[i\right]=dp\left[i\right]+dp\left[i\right]+1$
②：如果这个数是出现过的，那么所有子序列就是：原来 i−1 $i-1$的所有子序列 + $+$把所有原来 i−1 $i-1$的子序列的最后一位换成 x $x$，还要减去重复的，
比如有 1,2,3,4,5,4 $1,2,3,4,5,4$
1,2,3 $1,2,3$所有的子序列： {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3} $\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}$后面再加一个 4 $4$的情况 {1,4},{2,4},{3,4},{1,2,4},{1,3,4},{2,3,4},{1,2,3,4} $\{1,4\},\{2,4\},\{3,4\},\{1,2,4\},\{1,3,4\},\{2,3,4\},\{1,2,3,4\}$
那么这个 4 $4$到底是从前一个来还是从后一个来喃？两种情况只能选一种，而且从上面阔以得出，重复的就只有这里 7 $7$种
所以转移方程是：
dp[i]=dp[i−1]+dp[i−1]−dp[前一个位置−1] $dp\left[i\right]=dp[i-1]+dp[i-1]-dp[前一个位置-1]$

我用的 map $map$来标记上一次出现的位置

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
const int MOD=1e9+7;
long long dp[maxn];
int main()
{
    int N;
    while(cin>>N)
    {
        map<int,int>Mp;
        memset(dp,0,sizeof(dp));
        int t;
        for(int i=1;i<=N;i++)
        {
            cin>>t;
            if(Mp[t]==0)dp[i]=(dp[i-1]<<1)+1;
            else dp[i]=(dp[i-1]<<1)-dp[Mp[t]-1];
            dp[i]=(dp[i]+MOD)%MOD;
            Mp[t]=i;
        }
        cout<<dp[N]<<endl;
    }
}