[CEOI2015 Day1] 卡尔文球锦标赛
题目描述
译自 CEOI2015 Day1 T2「Calvinball championship」
一场卡尔文球比赛会有 $n$ 名选手参与，他们的编号分别为 $1\dots n$，分为若干个非空的球队。我们规定球队之间按照每个球队编号最小的选手的编号排序，并且以从 1 开始的连续整数编号。
举个栗子，譬如 1 号选手自己成一队，2, 3 和 5 号选手成一队，4 和 6 号选手成一队。
> $\ \texttt{1}$
> $\ \texttt{2 3 5}$
> $\ \texttt{4 6}$
那么 1 号选手的球队就是 1 号球队，2 号选手的球队就是 2 号球队，4 号选手的球队就是 3 号球队。
> $\ \texttt{1|1}$
> $\ \texttt{2|2 3 5}$
> $\ \texttt{3|4 6}$
每个人每天会选择不同的球队，我们可以在记录时省略选手的编号，仅记录每个位置对应选手所属球队编号的序列（上述例子为 1 2 2 3 2 3），因为每天的选手是一样的。当可能的选择方案全部被使用过后，锦标赛就结束了。
由于选择方案十分多，选择困难症患者纷纷表示力不从心。今年，我们决定根据记录的序列的字典序来选择方案。因此，第一天，所有人都在一个队 1 1 1 1 1；第二天，所有人都与 6 号针锋相对 1 1 1 1 1 2……在最后一天，所有人互相打响战争 1 2 3 4 5 6。
对于给定的球队记录，请你算出将会在未来的哪一天使用该记录。输出这个数字对 $1\ 000\ 007$ 取余的结果。
输入格式
第一行，一个正整数 $n(1 \leq n \leq 10\ 000)$。
第二行，$n$ 个以空格分隔的正整数，表示任务所给的球队记录。
输出格式
输出一个正整数，表示任务所给的球队记录将会被使用的天数对 $1\ 000\ 007$ 取余的结果。第一天的天数为 1。
样例 #1
样例输入 #1
3
1 2 2
样例输出 #1
4
提示
请注意，三人比赛中可能的选择有 1 1 1 1 1 2 1 2 1 1 2 2 和 1 2 3。
数据范围与提示
| 数据点 | $1-3$ | $4-5$ | $6-7$ | $8-10$ |
|---|---|---|---|---|
| $n\le$ | $14$ | $100$ | $1\ 000$ | $10\ 000$ |
考虑数位dp.设f(i,j,0/1)表示前i位，最高数字为j,0表示与前i位不同，1表示与前i位相同的序列数。
f(i+1,j,0)+=f(i,j,0)j;
f(i+1.j+1,0)+=f(i,j,0);
f(i+1，j,0)+=f(i,j,1)(a[i+1]-1);
a[i+1]==j+1?f(i+1,j+1,1):f(i+1,j,1)+=f(i,j,1)
#include<bits/stdc++.h>
#define int long long
#define b i&1^1
#define c i&1
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
const int N=10005,p=1000007;
int f[2][N][2];
int a[N],s=1;
signed main(){
int n;
cin>>n;
rep(i,1,n) cin>>a[i];
f[1][1][1]=1;
for(int i=1;i<n;i++)
for(int j=1;j<=i;j++){
f[c][j][0]%=p,f[c][j][1]%=p;
f[b][j][0]+=f[c][j][0]*j;
f[b][j+1][0]+=f[c][j][0];
f[b][j][0]+=f[c][j][1]*(a[i+1]-1);
(a[i+1]==j+1?f[b][j+1][1]:f[b][j][1])+=f[c][j][1];
f[c][j][0]=f[c][j][1]=0;
}
rep(j,1,n){
int i=n;
f[c][j][0]%=p;s+=f[c][j][0];
s%=p;
}
cout<<s;
}