CF1781B.Going to the Cinema
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
A company of n people is planning a visit to the cinema. Every person can either go to the cinema or not. That depends on how many other people will go. Specifically, every person i said: "I want to go to the cinema if and only if at least ai other people will go, not counting myself". That means that person i will become sad if:
- they go to the cinema, and strictly less than ai other people go; or
- they don't go to the cinema, and at least ai other people go.
In how many ways can a set of people going to the cinema be chosen so that nobody becomes sad?
输入格式
Each test contains multiple test cases. The first line contains the number of test cases t ( 1≤t≤104 ). The description of the test cases follows.
Each test case consists of two lines. The first line contains a single integer n ( 2≤n≤2⋅105 ) — the number of people in the company.
The second line contains n integers a1,a2,…,an ( 0≤ai≤n−1 ) — integers from peoples' claims.
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 .
输出格式
For each test case, print a single integer — the number of different ways to choose a set of people going to the cinema so that nobody becomes sad.
输入输出样例
输入#1
4 2 1 1 7 0 1 2 3 4 5 6 8 6 0 3 3 6 7 2 7 5 3 0 0 3 3
输出#1
2 1 3 2
说明/提示
In the first test case, both people want to go to the cinema if and only if the other person goes. There are two valid options: either both people go, or neither of them goes. However, if just one of them goes, both will be sad.
In the second test case, everyone has to go to the cinema. In any other case, someone will be sad.
In the third test case, there are three valid options: person number 2 goes to the cinema; or persons with indices 2,3,4,7 go; or all eight people go.