是时候该开垦皇帝荒地了 题意 有 nnn 根小木棍，长度分别为 a1,a2,⋯,ana_{1} , a_{2} , ⋯ , a_{n}a1 ,a2 ,⋯,an 。从这 nnn 根木棍中选出 mmm 根 ( m≥3m≥3m≥3 )，它们能拼成一个多边形当且仅当所有选出木棍的长度之和大于最长木棍长度的两倍。 要求计算出有多少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形，答案对 998244353998244353998244353 取模 解析 不妨将所有给定木棍根据其长度 aia_{i}ai 排序，假设第 iii 根木棍被选择且其长度最大，则需要在前 i−1i-1i−1 根木棍中选取部分，使选择的木棍长度和大于 aia_{i}ai ，这个无法直接求，不过我们可以考虑求其补集。即在前 i−1i-1i−1 根木棍中选取部分，使其长度和小于等于 aia_{i}ai 。 这一转换后的问题显然可以用动态规划处理，记 dpi,jdp_{i,j}dpi,j 表示前 iii 根木棍中选取若干，使其长度和为 jjj 的方案数，有 dpi,j=dpi−1,j+dpi−1,j−aidp_{i,j} = dp_{i - 1 , j} + dp_{i - 1 , j - a_{i}}dpi,j =dpi−1,j +dpi−1,j−ai 注意 ai>ja_{i} > jai >j 时，后一项视为0.最后用所用的所有选取方案数减去 2n2^n2n 减去不合法的部分即可 答案