链接
题意:
给你一个数字n,然后有一个长度为n的数列,这个数列的第 i 项值时某个数列的前 i 项的最大值减去最小值的到的结果,问你用着n个数字能构造出来多少种长度为n的数列。
分析:
首先我们考虑一下一定没有答案的方案:
- 如果开头不是0,或者结尾不是n-1一定没有答案
- 如果整个序列不是单调递增一定没有答案
- 如果差值小于序列长度-1,一定没有答案(长度为x,差值最小这x个数分别是1,2..x,这样差值为x-1所以差值不会小于序列长度-1)
然后我们分析:我们刚拿到这个问题,不知道如何解决,那么我们得找到一个突破口,这个突破口最最后(n-1)的地方,
我们看,当出现n-1时,该位置,一定放了(1或者n)这点是毋容置疑的。
然后我们该位置有两种放法(假设放了1)那么后面等于(n-1)的先空出来计数有num个空,
再往前看,如果前一个数为(n-2)那么我们肯定就是可以放(2或者n)这样该能使的满足差值为(n-2),(假设我们放了2)
然后跟上面一样,在往前看如果前一个数为(n-4),那么我们想这个位置可以放的数(4或者n)如果放了4,但是我们还有3,他肯定在这个位置之后放, 那就用到我们前面记录的num个空了,在这num个空中选一个放4即可。(放n同理也要把3放进空中)。
那么我们就得出:
int _;
scanf("%d", &_);
while (_--)
{
scanf("%lld", &n);
ll flag = 1;
for(int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
if(i == 1)
{
if(a[i] != 0) flag = 0;///不是0开头一定没有答案
}
else
{
if(a[i] < a[i - 1]) flag = 0;///不单调递增 一定没有答案
if(a[i] < i - 1) flag = 0;///这个是差值小于数量一定没有答案
}
}
if(a[n] != n - 1) flag = 0;//最终差值不为n-1一定没有答案
if(flag == 0) puts("0");//没有答案输出0
else
{
ll ans = 1;
ll num = 0;
for(int i = n; i > 1; i--)
{
int j = i;
while(j > 1 && a[j] == a[i]) j--, num++;/// 相同的数量
num--;
for(int k = 1; k <= a[i] - a[j] - 1; k++)
{
ans = ans * num % MOD;/// 选取最小的数 有num位置可以选择
num--;
}
ans = ans * 2 % MOD;/// 两种选择
i = j + 1;///转移到与其不同的敌方。
}
printf("%lld\n", ans);
}
}