好题 题意非常明了

设f[n][m]为  相差为n 迭代m次计算得到答案

则可以知道 f[n][m]=sigma(i=1~n) f[i][m-1]+sigma(i=1~n-1)f[i][1]    一式

设f[n-1][m]=sigma(i=1~n-1)f[i][m-1]+sigma(i=1~n-2)f[i][1]     二式

用一式-二式

f[n][m]-f[n-1][m]=f[n][m-1]+f[n-1][1]

f[n][m]=n-1+f[n-1][m]+f[n][m-1]

设g[n][m]为f[n][m]+n

则原式转换为g[n][m]=g[n-1][m]+g[n][m-1]

那么 打一张表 可以看出规律

发现g[n][m]可以表示为组合数快速计算 然后求逆远的时候我们可以使用费马小定理 a^(p-2)

 

 


elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论