简要题意
给你一个 \(n\times m\) 的棋盘，你需要在棋盘上放置两个颜色不同的皇后，使得它们互相攻击。求方案数。
\(1 \leq n,m \leq 10^6\)
思路
下面假设 \(n\leq m\)。
首先发现，两个互相攻击的皇后大致有下面三种情况：
- 在同一行，方案数为 \(\binom{n}{1}\operatorname{A}^{2}_{m}=nm(m-1)\)。
- 在同一列，方案数为 \(\binom{m}{1}\operatorname{A}^{2}_{n}=nm(n-1)\)。
- 在同一个斜线上，这个比较复杂：
设所在的斜线的长度为 \(S\)，则方案数为 \(2A^{2}_{S}=2S(S-1)\)（因为斜线方向有两种）。
斜线长度一共有：
\[1,2,\cdots,n-2,n-1,\underbrace{n,n,\cdots,n,n}_{m-n+1},n-1,n-2,\cdots,2,1 \]所以同一个斜线的方案数就是：
\[\begin{aligned} &2(n(n-1)(m-n+1)+2\sum_{i=1}^{n-1}{i(i-1)})\\ &=2(n(n-1)(m-n+1)+2(\sum_{i=1}^{n-1}i^2-\sum_{i=1}^{n-1}i))\\ &=2(n(n-1)(m-n+1)+2(\frac{n(n-1)(2n-1)}{6}-\frac{n(n-1)}{2}))\\ &=2(n(n-1)(m-n+1)+2(\frac{n(n-1)(2n-4)}{6}))\\ &=2(n(n-1)(m-n+1)+\frac{n(n-1)(2n-4)}{3})\\ &=2\cdot\frac{3n(n-1)(m-n+1)+n(n-1)(2n-4)}{3}\\ &=2\cdot\frac{n(n-1)(3m-3n+3+2n-4)}{3}\\ &=\frac{2n(n-1)(3m-n-1)}{3} \end{aligned} \]于是这道题就做完了。最后答案是：
\[nm(m-1)+nm(n-1)+\frac{2n(n-1)(3m-n-1)}{3} \]单次计算时间复杂度 \(O(1)\)。
代码
点击查看代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m;
signed main(){
while(cin>>n>>m&&n&&m){
if(n>m) swap(n,m);
int row=n*m*(m-1);
int col=m*n*(n-1);
int xie=2*n*(n-1)*(3*m-n-1);
xie/=3;
cout<<(row+col+xie)<<'\n';
}
return 0;
}