/ Vijos / 题库 /

排列统计

排列统计

背景

Orz5-4 count

描述

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

数据保证了至少有一个排列满足B序列。

格式

输入格式

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

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

输出格式

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

样例1

样例输入1

3
0 1 3

样例输出1

3

限制

对于20%的数据,有N≤8;
对于30%的数据,有N≤11且答案不大于20000;
对于50%的数据,有N≤100;
对于100%的数据,有N≤2000。

时限1s。

提示

对于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序列。

信息

ID
1660
难度
7
分类
组合数学 | 高精度 点击显示
标签
递交数
442
已通过
73
通过率
17%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

Orz教主第五次模拟赛