开发者社区> 问答> 正文

遇到一个填数问题,求解答

有 m 个格子,编号为 1,2…m,每个格子可以填 1,2...n 中的任意一个数。定义这 m 个格子上的数都是“好的”,仅当对于任意一个编号为 i 的格子,编号大于 i 的格子上的数都大于等于 i 号格子上的数。求有多少个填数方案,满足这 m 个格子中填的数是“好的”,答案对 P 取模。三行分别输入三个整数,m、n、P,分别表示有 m 个格子、填入的最大数字 n和模 P。(保证 1<=n,m<=1e18,2<=P<=1e5 且 P是质数)输出一个整数表示答案对 P 取模的结果。

展开
收起
游客4skzfvnrxrzbi 2021-12-23 17:11:43 491 0
1 条回答
写回答
取消 提交回答
  • “对于任意一个编号为 i 的格子,编号大于 i 的格子上的数都大于等于 i 号格子上的数”可以转化为m个格子上的数是单调不减的。令cnt_i表示i这个数在m个格子中的出现次数,可以发现一组∑ cnti=m(i ∈ [1,n]) 唯一对应着一个单调不减的填数方案。由插板法可知,n 个非负整数和为 m 的方案数为 (n+m-1,n-1)。所以答案就是(n+m-1,n-1),n,m 很大时需要用卢卡斯定理。 因此输入:2 2 11 输出:3

    2021-12-23 18:57:51
    赞同 展开评论 打赏
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载