问题2935--排列(Permutation)

2935: 排列(Permutation)

时间限制: 7 Sec  内存限制: 512 MB
提交: 3  解决: 3
[提交] [状态] [讨论版] [命题人:]

题目描述

zpy有一个长度为n的排列a,定义一个a的亲密序列b,b的长度为n-1,对于任意bi满足
if (ai>ai+1) bi=0
else bi=1
现在给出一个长度为n-1的亲密序列b,请你求出有多少个长度为n的排列a满足它的亲密序列是b

输入

第一行输入一个整数T,表示共有T组数据
对于每一组数据,
第一行输入一个整数n
第二行输入一个长度为n-1的亲密序列b

输出

对于每一组数据,输出符合要求的排列的数量

样例输入 Copy

2
3
1 0
5
1 0 0 1

样例输出 Copy

2
11

提示

100%数据  1<=n<=50  2<=n<=5000  保证n>300的数据的组数不会超过20

来源/分类