遇到一个填数问题，求解答
有 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 取模的结果。
展开
收起
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赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
