Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom3月前

04/5
15:16
组合数/lucas 高精度

[bzoj 4807] 車

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

众所周知,車是中国象棋中最厉害的一子之一,它能吃到同一行或同一列中的其他棋子。車跟車显然不能在一起打起来,于是rly一天又借来了许多许多的車在棋盘上摆了起来……他想知道,在N×M的矩形方格中摆最多个数的車使其互不吃到的情况下方案数有几种。但是,由于上次摆炮摆得实在太累,他为了偷懒,打算增加一个条件:对于任何一个車A,如果有其他一个車B在它的上面(車B行号小于車A),那么車A必须在車B的右边(車A列号大于車B)。
棋子都是相同的。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

一行,两个正整数N和M。
N<=1000000,M<=1000000

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

一行,输出方案数的末尾50位(不足则直接输出)。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

2 2

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

1

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

显然答案是 c(max(n,m), min(n,m)),质因数分解之后高精度即可

 

[bzoj 4807] 車