炮(cannon)

【题⽬描述】 众所周知，双炮叠叠将是中国象棋中很厉害的⼀招必杀技。炮吃⼦时必须 隔⼀个棋⼦跳吃，即俗称“炮打隔⼦”。 炮跟炮显然不能在⼀起打起来，于是rly ⼀天借来了许多许多的炮在棋盘上摆了起来……他想知道，在N×M的矩形⽅格 中摆若⼲炮（可以不摆）使其互不吃到的情况下⽅案数有⼏种。 棋⼦都是相同的。

【输⼊说明】 ⼀⾏，两个正整数N和M。

【输出说明】 ⼀⾏，输出⽅案数mod 999983。

【样例输⼊】 1 3

【样例输出】 7

【数据范围】 对于40%的数据,N<=4,M<=4 对于70%的数据,N<=100,M<=8 对于100%的数据,N<=100,M<=10

题解：

**AHOI2009中国象棋** 原题三维状态的DP⾞(rook)【题⽬描述】 众所周知，⾞是中国象棋中最厉害的⼀⼦之⼀，它能吃到同⼀⾏或同⼀列 中的其他棋⼦。⾞跟⾞显然不能在⼀起打起来，于是rly⼀天又借来了许多许多 的⾞在棋盘上摆了起来……他想知道，在N×M的矩形⽅格中摆最多个数的⾞使 其互不吃到的情况下⽅案数有⼏种。但是，由于上次摆炮摆得实在太累，他为 了偷懒，打算增加⼀个条件：对于任何⼀个⾞A，如果有其他⼀个⾞B在它的上 ⾯（⾞B⾏号⼩于⾞A），那么⾞A必须在⾞B的右边（⾞A列号⼤于⾞B）。 棋⼦都是相同的。 【输⼊说明】 ⼀⾏，两个正整数N和M。 【输出说明】 ⼀⾏，输出⽅案数的末尾50位（不⾜则直接输出）。 【样例输⼊】 2 2【样例输出】 1 【数据范围】 对于20%的数据，N<=10，M<=10。 对于40%的数据，N<=40，M<=40。 对于70%的数据，N<=10000，M<=10000。 对于100%的数据，N<=1000000，M<=1000000。

题解：

**排列组合C(n,m) + 质因数分解(快速质因数分解John M. Pollard方法 n ^(1/4)) + 高精乘**如果 n < m 交换一下一开始写的递推 O(m * (n - m +１))　后来发现可以矩阵乘法，　再后来发现可以两个ｓｕｍ转换前缀和。。。。然而不是正解。。。。