题解 P4798 【[CEOI2015 Day1]卡尔文球锦标赛】

# 题意分析 显然，一个序列中如果要出现k这个数，为了保证序列合法，那么在他之前的位置中1~k-1必定都出现过。 假如我们已经得到了前面的元素，剩下i个元素待确定，前面的最大值是j，那么剩下的方案数显然只与i和j有关。 设$f[i][j]$表示当前待确定长度为i，前面的最大值是j。 我们就可以考虑每一个位置单独计算方案数。 我们从后往前考虑每一个位置假设它前面与原序列完全符合的情况下，有多少序列字典序比原序列小，显然$(j−1)$∗$f[i][j]$个。 每个1从这里开始第一次出现新的数k，所以方案数为1，然后1后面的连续一段可以选择1~k的数，所以方案数是k。 递推关系：后一位放k，当前这位就有k种放法；后一位放k+1，只有一种放法。 所以我们可以枚举前面的的最大值k，f[i][k]= k ∗ f[i−1][k]+f[i−1][k+1] ## Coding ``` #include<bits/stdc++.h> #define ll long long using namespace std; inline int read() { int x=0; char c=getchar(); bool flag=0; while(c<'0'||c>'9') {if(c=='-')flag=1;c=getchar();} while(c>='0'&&c<='9'){x=(x+(x<<2)<<1)+ c-'0';c=getchar();} return flag?-x:x; } const int N=1e4+5,mod=1e6+7; int n,now,ans,a[N],maxn[N],f[2][N]; int main() { n=read(); for(int i=1;i<=n;++i) a[i]=read(),f[0][i]=1; for(int i=2;i<=n;++i) maxn[i]=max(maxn[i-1],a[i-1]); for(int i=n;i>=1;--i) { ans=(ans+(ll)f[now][maxn[i]]*(a[i]-1)%mod)%mod; for(int k=0;k<i;++k) f[!now][k]=((ll)k*f[now][k]%mod+f[now][k+1])%mod; now=!now; } printf("%d\n",(ans+1)%mod); } ```