求大神解释一下 D 题矩阵填数的思路

1 answer(s)

1

杨氏矩阵的钩子公式，n和m都可以是1e6的，复杂度是o(n+m)的。

  • 带个快速幂的log ，刚才说错了，但是仍然可以是1e6的

  • o(nm)怎么降到o(n+m)的

  • 是不是先求组合数，钩子长度为k(1<=k<=n+m-1)的种数

  • 是的，对于一种钩子的长度，他的坐标（x，y）是一条斜线，你可以很容易计算个数，加上快速幂就好了。

  • 其实也不用log的，因为一列的钩子和另一列的钩子 就差一个东西

  • 不过(nm)！这个貌似要O(nm)？？

  • nm的阶乘有快速的公式吗

  • 钩子公式你没有理解吧，是(n+m)！

  • n*m的矩阵，格子个数不是n*m吗

  • 你的代码里写的也是n*m

  • long long ans=1; for(int i=1;i<=n*m;i++) { ans=ans*i%mod; }

  • 那是我懒的推了，直接写，反正n也不大，

  • 添加评论
  • ✖reply

write answer 切换为英文 切换为中文

转发分享

▲