307545: CF1371E2. Asterism (Hard Version)
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Asterism (Hard Version)
题意翻译
这是问题 E 的困难版本。它与 E1 的唯一区别在于 $n$ 和 $a_i$ 的大小。 Yuzu~~soft~~ 是一个收集糖果的女孩。最初,她有 $x$ 个糖果。有 $n$ 个敌人,编号从 $1$ 到 $n$,第 $i$ 个敌人有 $a_i$ 个糖果。 Yuzu 需要确定一个 $1$ 到 $n$ 的排列 $P$。在此之后,她按照以下规则挑战敌人: - 如果 Yuzu 的糖果不少于编号为 $P_i$ 的敌人的糖果,她会赢得一个糖果。否则,她什么也得不到。 - 得到的糖果加入她拥有糖果的总数量中,可以在下次挑战中使用。 Yuzu 想赢得所有挑战。有多少种排列 $P$? 然而,这个问题太简单了。设 $f(x)$ 为 Yuzu 初始有 $x$ 个糖果时的,合法的排列总数。给定质数 $p \leq n$,那么你需要求出有多少个 $x$ 使得 $p \nmid f(x)$,其中 $p \nmid f(x)$ 表示 $f(x)$ 不能被 $p$ 整除。 $2 \leq p \leq n \leq 10^5,1 \leq a_i \leq 10^9$ 翻译 by Meatherm题目描述
This is the hard version of the problem. The difference between versions is the constraints on $ n $ and $ a_i $ . You can make hacks only if all versions of the problem are solved. First, Aoi came up with the following idea for the competitive programming problem: Yuzu is a girl who collecting candies. Originally, she has $ x $ candies. There are also $ n $ enemies numbered with integers from $ 1 $ to $ n $ . Enemy $ i $ has $ a_i $ candies. Yuzu is going to determine a permutation $ P $ . A permutation is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ \{2,3,1,5,4\} $ is a permutation, but $ \{1,2,2\} $ is not a permutation ( $ 2 $ appears twice in the array) and $ \{1,3,4\} $ is also not a permutation (because $ n=3 $ but there is the number $ 4 $ in the array). After that, she will do $ n $ duels with the enemies with the following rules: - If Yuzu has equal or more number of candies than enemy $ P_i $ , she wins the duel and gets $ 1 $ candy. Otherwise, she loses the duel and gets nothing. - The candy which Yuzu gets will be used in the next duels. Yuzu wants to win all duels. How many valid permutations $ P $ exist? This problem was easy and wasn't interesting for Akari, who is a friend of Aoi. And Akari made the following problem from the above idea: Let's define $ f(x) $ as the number of valid permutations for the integer $ x $ . You are given $ n $ , $ a $ and a prime number $ p \le n $ . Let's call a positive integer $ x $ good, if the value $ f(x) $ is not divisible by $ p $ . Find all good integers $ x $ . Your task is to solve this problem made by Akari.输入输出格式
输入格式
The first line contains two integers $ n $ , $ p $ $ (2 \le p \le n \le 10^5) $ . It is guaranteed, that the number $ p $ is prime (it has exactly two divisors $ 1 $ and $ p $ ). The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ $ (1 \le a_i \le 10^9) $ .
输出格式
In the first line, print the number of good integers $ x $ . In the second line, output all good integers $ x $ in the ascending order. It is guaranteed that the number of good integers $ x $ does not exceed $ 10^5 $ .
输入输出样例
输入样例 #1
3 2
3 4 5
输出样例 #1
1
3
输入样例 #2
4 3
2 3 5 6
输出样例 #2
2
3 4
输入样例 #3
4 3
9 1 1 1
输出样例 #3
0
输入样例 #4
3 2
1000000000 1 999999999
输出样例 #4
1
999999998