• 微信公众号：美女很有趣。 工作之余，放松一下，关注即送10G+美女照片！

# 题解 茅山道术

4小时前 2次浏览

Code:
``````#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 1000010
#define ll long long
#define reg register int
//#define int long long

char buf[1<<21], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
int ans=0, f=1; char c=getchar();
while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
return ans*f;
}

int n;
int c[N];
const ll mod=1e9+7;
inline void md(ll& a, ll b) {a+=b; a=a>=mod?a-mod:a;}

int pre[N], lst[N], bkp[N], tot;
ll dp[2010][2010];
void solve() {
dp[0][0]=1;
memset(lst, -1, sizeof(lst));
memcpy(bkp, c, sizeof(c));
for (int pos2=1; pos2<=n; ++pos2)
if (bkp[pos2-1]!=bkp[pos2]) c[++tot]=bkp[pos2];
for (int i=1; i<=tot; ++i) {
pre[i]=lst[c[i]];
lst[c[i]]=i;
}
//cout<<"pre: "; for (int i=1; i<=tot; ++i) cout<<pre[i]<<' '; cout<<endl;
for (int i=1; i<=tot; ++i) {
for (int j=0; j<i; ++j) {
dp[i][j] = dp[i-1][j];
if (pre[i]>=j) dp[i][i]=(dp[i][i]+dp[i-1][j])%mod;
}
}
ll ans=0;
for (int i=0; i<=tot; ++i) ans=(ans+dp[tot][i])%mod;
printf("%lldn", ans);
exit(0);
}
}

int pre[N], lst[N], bkp[N], tot;
ll dp[N];
inline void upd(int i, ll dat) {dat%=mod; for (; i<=tot+1; i+=i&-i) md(dp[i], dat);}
inline ll query(int i) {ll ans=0; for (; i; i-=i&-i) md(ans, dp[i]); return ans;}
void solve() {
memset(lst, -1, sizeof(lst));
memcpy(bkp, c, sizeof(c));
for (int pos2=1; pos2<=n; ++pos2)
if (bkp[pos2-1]!=bkp[pos2]) c[++tot]=bkp[pos2];
for (int i=1; i<=tot; ++i) {
pre[i]=lst[c[i]];
lst[c[i]]=i;
}
upd(1, 1);
//cout<<"pre: "; for (int i=1; i<=tot; ++i) cout<<pre[i]<<' '; cout<<endl;
ll tem;
for (int i=1; i<=tot; ++i) if (~pre[i]) {
tem=query(pre[i]+1);
if (tem) upd(i+1, tem);
}
printf("%lldn", query(tot+1));
exit(0);
}
}

signed main()
{
freopen("magic.in", "r", stdin);
freopen("magic.out", "w", stdout);