简要题意

给你一个 \(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;
}