【在线编程产品介绍】

阿里云开发者社区在线编程：

免费刷题大神器，助你拿到好offer

周赛月赛不停歇，做题还能领奖品

大赛笔试全真题，常做常新有惊喜

点击链接开始产品体验：https://developer.aliyun.com/coding

本文为大家介绍的是“112.填数问题”的解法探究。先来看一下题目内容：

题目详情

等级：中等
知识点：数论、数学
查看题目：填数问题

有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
输入：
2
2
11
输出：
3

解题方法：

“对于任意一个编号为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很大时需要用卢卡斯定理。

复杂度O(logp n)

看完之后是不是有了答题思路了呢，快来练练手吧：112.填数问题

在线编程周赛、月赛火热进行中，更有限时答题活动，社区定制卫衣、双肩背包、机械键盘等你来拿~每天都有好礼相送~点击了解周赛详情：在线编程3月份比赛正式开启！机械键盘等你拿！