F. Marmots (hard)

你的任务与_简单_版本完全相同。但这次，土拨鼠在响应海蒂的请求前，会从其随机数中减去村庄的人口 #cf_span[P]。 此外，现在有些村庄的人口甚至只有一个人，即 。 你能帮助海蒂判断一个村庄遵循的是泊松分布还是均匀分布吗？ 与简单版和中等版相同。但请注意，现在 #cf_span[1 ≤ P ≤ 1000]，且土拨鼠可能提供正整数或负整数。 请为每个村庄输出一行，顺序与输入中给出的顺序一致。若村庄的分布为泊松型，则输出 _poisson_；若答案来自均匀分布，则输出 _uniform_。 ## Input 与简单版和中等版相同。但请注意，现在 #cf_span[1 ≤ P ≤ 1000]，且土拨鼠可能提供正整数或负整数。 ## Output 请为每个村庄输出一行，顺序与输入中给出的顺序一致。若村庄的分布为泊松型，则输出 _poisson_；若答案来自均匀分布，则输出 _uniform_。 [samples]

Given: - A sequence of $ n $ integers $ a_1, a_2, \dots, a_n $, each representing a response from a marmot in a village. - Each response is of the form $ r_i - P $, where $ r_i $ is a random sample from either: - A **Poisson distribution** with parameter $ \lambda = P $, or - A **uniform distribution** over $ \{1, 2, \dots, P\} $. - $ 1 \leq P \leq 1000 $, and $ P $ is the population of the village. - Responses $ a_i $ can be positive, negative, or zero. Objective: For each village, determine whether the underlying distribution of the *original* random samples $ r_i $ is Poisson or uniform, based on the observed responses $ a_i = r_i - P $. Formally: Let $ S = \{a_1, a_2, \dots, a_n\} $ be the multiset of observed responses. Define the unobserved samples as $ r_i = a_i + P $. - If $ r_i \sim \text{Poisson}(P) $, then $ r_i \in \mathbb{Z}_{\geq 0} $, and $ \mathbb{E}[r_i] = P $, $ \text{Var}(r_i) = P $. - If $ r_i \sim \text{Uniform}\{1, 2, \dots, P\} $, then $ r_i \in \{1, 2, \dots, P\} $, $ \mathbb{E}[r_i] = \frac{P+1}{2} $, $ \text{Var}(r_i) = \frac{P^2 - 1}{12} $. Thus, the observed responses $ a_i = r_i - P $ satisfy: - Under Poisson: $ a_i \in \{-P, -P+1, \dots\} $, $ \mathbb{E}[a_i] = 0 $, $ \text{Var}(a_i) = P $. - Under Uniform: $ a_i \in \{1 - P, 2 - P, \dots, 0\} $, $ \mathbb{E}[a_i] = \frac{1 - P}{2} $, $ \text{Var}(a_i) = \frac{P^2 - 1}{12} $. Decision Rule: Compute sample mean $ \bar{a} = \frac{1}{n} \sum_{i=1}^n a_i $ and sample variance $ s^2 = \frac{1}{n-1} \sum_{i=1}^n (a_i - \bar{a})^2 $ (or use population variance if preferred, but consistently). - If $ |\bar{a}| < \varepsilon $ and $ s^2 \approx P $, classify as **poisson**. - If $ \bar{a} \approx \frac{1 - P}{2} $ and $ s^2 \approx \frac{P^2 - 1}{12} $, classify as **uniform**. Use a threshold $ \varepsilon $ (e.g., $ 0.1 $) to distinguish $ \bar{a} \approx 0 $ from $ \bar{a} \approx \frac{1-P}{2} $. Since $ P \geq 1 $, $ \frac{1-P}{2} \leq 0 $, and for $ P > 1 $, $ \left| \frac{1-P}{2} \right| \geq 0.5 $, so $ |\bar{a}| < 0.1 $ strongly suggests Poisson. **Formal Output Rule:** For each village with population $ P $ and observed responses $ a_1, \dots, a_n $: - Compute $ \bar{a} $ and $ s^2 $. - If $ |\bar{a}| \leq 0.1 $ and $ |s^2 - P| \leq \delta \cdot P $ (for small $ \delta $, e.g., 0.2), output **poisson**. - Else if $ \left| \bar{a} - \frac{1 - P}{2} \right| \leq 0.1 $ and $ \left| s^2 - \frac{P^2 - 1}{12} \right| \leq \delta \cdot \frac{P^2 - 1}{12} $, output **uniform**. - (In practice, due to distinct expectations, comparing $ |\bar{a}| $ to 0.1 suffices for high accuracy.) **Final Decision (Simplified):** $$ \boxed{ \begin{cases} \text{poisson} & \text{if } |\bar{a}| \leq 0.1 \\ \text{uniform} & \text{otherwise} \end{cases} } $$