炼石计划NOIP模拟赛第4套题目T2 组合数问题

ID: 842

传统题

1000ms

256MiB

尝试: 0

已通过: 0

难度: (无)

上传者:

Hydro

标签>

炼石

T2 组合数问题

题目信息

时间限制: 1.5s

空间限制: 512M

输入文件: fc.in

输出文件: fc.out

题目描述

组合数 $\binom{n}{m}$ 表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子，从 $(1,2,3)$ 三个物品中选择两个物品可以有 $(1,2),(1,3),(2,3)$ 这三种选择方法。根据组合数的定义，我们可以给出计算组合数 $\binom{n}{m}$ 的一般公式：

\binom{n}{m}=\frac{n!}{m!(n-m)!}

其中 $n!=1\times2\times\cdots\times n$ ；特别地，定义 $0!=1$ 。

看到这里，你可能会想到，某年NOIP不是也有道组合数问题吗，题目描述甚至还很像！？

可惜两道题有亿点点区别。

我们利用组合数定义一下 $f(n,k)$ ，他等于：

\sum_{x_1=0}^n \binom{n}{x_1} \sum_{x_2=0}^{x_1} \binom{x_1}{x_2} \sum_{x_3=0}^{x_2} \binom{x_2}{x_3} \dots \sum_{x_k=0}^{x_{k-1}} \binom{x_{k-1}}{x_k}

特别地，规定 $f(n,0)=1$ 。

然后麻烦你求解：

\sum_{i=0}^n f(f(n,i),i) \mod 998244853

输入格式

本题含有多组数据

第一行为一个整数 $T$ ，表示数据组数。

对于每组数据，一行一个整数，表示 $n$ 。

输出格式

对于每组数据，一行一个整数，表示答案。

样例

输入1

输出1

5
909927378
208415843

数据范围与提示

对于所有的测试点, $T \le 5, n \le 2 \times 10^5$ 。

对于 $20 \%$ 的数据, 满足 $n \le 10$
对于 $60\%$ 的数据, 满足 $n \le 10^3$
对于 $100 \%$ 的数据, 满足 $n \le 2 \times 10^5$

#C0402. 炼石计划NOIP模拟赛第4套题目T2 组合数问题