NOIP 2016系列解题报告 – [题组/NOIP]

Day2 T1 组合数问题

你可以点击这个链接下载全部的AC代码

题目传送门 (LOJ)

题解 :

​ 数据范围2000, 递推求组合数,我们肯定要模一个什么数,遍观整题显然是 k,因为 \mod k = 0 的意义就是是 k 的倍数,稍加思考可以发现是 (n, m) 点左上方的所有 0 点数量的加和,我们维护组合数的同时直接递推出一个答案就可以

c[i][0] = 0, c[i][j] = c[i-1][j-1]+c[i-1][j]

ans[i][j] = -ans[i-1][j-1]+ans[i][j-1]+ans[i-1][j]+[c[i][j] = 0]

注意边界情况的特判,注意取取模。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注