2020-2021:teams:looking_up_at_the_starry_sky:杭电2018_第四场_b [CVBB ACM Team]

Warning: session_start(): open(/tmp/sess_8763628016f49c3c93d54fc2fd67614e, 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

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

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:looking_up_at_the_starry_sky:杭电2018_第四场_b [CVBB ACM Team]

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: 思路比较巧妙

2020-2021/teams/looking_up_at_the_starry_sky/杭电2018_第四场_b.txt · 最后更改: 2020/08/21 18:04 由 zzy