遇到一个求模的问题，求解答。
Jerry和Tom 在公园里感到很无聊，于是就开始研究起来题目了，Jerry 有一个n+1 个桶 (1<=n<=300)，这些桶的编号为0,1,2,...,n，然后让Tom 去构造这些桶(每个桶可以看作 list)，必须要满足以下的三个要求： 1.对于第 i 个桶里，它里面有 i 个数 ai，并且这些数不能大于 x(1<=ai<=300)。 2.对于第 i-1 个桶，它必须是第 i 个桶的子序列。 3.对于第 i 个桶，它的字典序要大于第 i-1 个桶。 问满足以上要求的方案有多少总，答案对 y(2<=y<=1e9) 取模。输入三行数据，分别为 n,x,y，意思同题意。输出一个数，表示最终的方案数，答案对y取模。
写回答
-
拿样例来说 2 3 100, 说明有 3 个桶，第 0 个桶一定是空的，那么符合条件的有以下 12 种方案： ({0},{1},{1,1}), ({0},{1},{1,2}), ({0},{1},{1,3}), ({0},{1},{2,1}), ({0},{1},{3,1}), ({0},{2},{2,1}), ({0},{2},{2,2}), ({0},{2},{3,1}), ({0},{3},{3,1}), ({0},{3},{3,2}), ({0},{3},{3,3})， 这只是简单的列举出了所有的情况，我们需要从中推出转移方程。以 {0},{2} 为例，要构造出第三个桶就相当于往第二个桶中插入一个数字；那么如果这个数字插在 2 的左边，一定是要比 2 大的数才可以，如果插到右边对于这个情况来说没有限制条件，如果对于位数较多的数列来说也要考虑到字典序的因素。所以我们考虑 fi[p] 中，i 表示当前的长度，j 表示取到的数字，p 表示有 p 个位置可插。一共有三种状态，当你的p没位置了就没有地方可插，那么这个数就不插了,dpi[i] +=dpi[p], 这里的第三维为i 是因为所有的数都比 j+1 小，所以插到哪里都是可以的，所以为 i。如果 p不为 0 的话说明有地方可插，这时可以考虑插在这个地方或者不插这个地方，如果不插这个地方 dpi[p-1]+=dpi[p]，如果插这个地方 dpi+1[p]+=dpi[p]，这里还需要乘以 p+1 是因为还有 p 个位置。
则输入：2 3 100 输出：122021-12-23 18:38:48赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
