有 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 取模的结果。
“对于任意一个编号为 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
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。