Warning: session_start(): open(/tmp/sess_8d515b6c78ec953af267ec4a89fe0a63, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/de2edb2fcb553ea79b79c722a4e13dbc.captchaip failed

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
2020-2021:teams:looking_up_at_the_starry_sky:杭电2018_第四场_b

分类：数学，分块

题意：求 $$ C_n^0+C_n^1+\dots + C_n^m $$ 询问T(1e5)次，n,m(1e5)

题解： $$ Ans(n,m)=2Ans(n-1,m-1)+C(n-1,m) $$ 求出$\sqrt{n}$行的答案，每次询问把n减到最近的一行上，然后推出答案。

时间复杂度 $O(n\sqrt{n})$

comment: 思路比较巧妙