排列统计

\(Description\)

对于给定的一个长度为n的序列{B[n]}，问有多少个序列{A[n]}对于所有的i满足：A[1]～A[i]这i个数字中有恰好B[i]个数字小等于i。其中{A[n]}为1～n的一个排列，即1～n这n个数字在序列A[I]中恰好出现一次。数据保证了至少有一个排列满足B序列。

\(Input\)

输入的第1行为一个正整数N，表示了序列的长度。

第2行包含N个非负整数，描述了序列{B[i]}。

\(Output\)

输出仅包括一个非负整数，即满足的{A[i]}序列个数。

\(Sample Input\)

3

0 1 3

\(Sample Output\)

\(Hint\)

【样例说明】

　　对于A序列为1～3的全排列分别对应的B序列如下（冒号左边为A序列，冒号右边为对应B的序列）

　　1 2 3：1 2 3

　　1 3 2：1 1 3

　　2 1 3：0 2 3

　　2 3 1：0 1 3

　　3 1 2：0 1 3

　　3 2 1：0 1 3

　　所以有3个满足的A序列。

【数据说明】

　　对于20%的数据，有N≤8；

　　对于30%的数据，有N≤11且答案不大于20000；

　　对于50%的数据，有N≤100；

　　对于100%的数据，有N≤2000。

解题思路

其实很容易发现，当且仅当 \(B_i - B_{i-1} = {0 , 1 , 2}\) 时才有解

因为考虑到 \(B_i\) 和 \(B_{i-1}\) 的关系，前者是后者产生的数列再加入一个新的数

为了方便表达，记产生的数列为 \(a_{1..n}\)

那么新加入一个数，记为x ，它至多可以给 \(B_i\) 贡献 1（\(x <= i\)），此时可贡献的数从上限 \(i-1\) 提升到 \(i\) ，如果之前有一个数恰好等于 i，那么它又可以给 \(B_i\) 贡献 1

然后就找不到可贡献的了，即 \(B_i + 2 \geq B_{i-1}\) 时才可能构造数列

现在考虑如何求得答案

设 \(f_i\) 表示前 \(1..i\) 满足条件的数列数目，\(k = B_{i-1} - B_i\)

\[f_i =
\left \{
\begin{aligned}
f_{i-1} & & (k=0) \\
f_{i-1}[(i-B_{i-1})+(i-1-B_{i-1})] & & (k=1) \\
f_{i-1}(i-B_{i-1}-1)^2 & & (k=2)
\end{aligned}
\right.
\]

要用高精度！！！

代码参考

#include<cstdio>

using namespace std;

typedef long long LL;

int b[2005] , n , ans[10005];

inline void mul(int x)

{

	int g = 0;

	for(register int i = 1; i <= ans[0]; i++)

	{

		ans[i] = ans[i] * x + g;

		g = ans[i] / 10;

		ans[i] = ans[i] % 10;

	}

	while(g)

	{

		ans[++ans[0]] = g;

		g = ans[ans[0]] / 10;

		ans[ans[0]] = ans[ans[0]] % 10;

	}

}

int main()

{

	scanf("%d" , &n);

 	for(register int i = 1; i <= n; i++) scanf("%d" , &b[i]);

 	ans[0] = ans[1] = 1;

 	for(register int i = 1; i <= n; i++)

 	{

 		if (b[i] - b[i-1] == 1) mul(i - b[i-1] + i - 1 - b[i - 1]);

 		else if (b[i] - b[i-1] == 2) mul((i - b[i - 1] - 1) * (i - b[i - 1] - 1));

	}

	for(register int i = ans[0]; i; i--) printf("%d" , ans[i]);

}

巴特西

JZOJ 排列统计