此题有Θ(T)\Theta(T)的做法,感谢lrc大佬讲解

已经得到了

ans1=Cm1An2=nm(n1)ans_1=C_m^1A_n^2=nm(n-1)

ans2=Cn1Am2=nm(m1)ans_2=C_n^1A_m^2=nm(m-1)

ans1ans_1ans2ans_2为在同一行与同一列互相攻击的皇后数

ans3ans_3为在同一斜列的互相攻击皇后数
显然

ans3=2×[A22+A32+...+An2×(mn+1)+...+A32+A22]ans_3=2\times[A_2^2+A_3^2+...+A_n^2\times(m-n+1)+...+A_3^2+A_2^2]

如何化简?将此式展开

ans3=[1×2+2×3+...+(n1)×n]×4+2n(n1)(mn)ans_3=[1\times2+2\times3+...+(n-1)\times n]\times4+2n(n-1)(m-n)

前半部分就像小学奥数中的通项求和问题了

ans3=i=1n1i(i+1)×4+2n(n1)(mn)ans_3=\sum_{i=1}^{n-1}{i(i+1)}\times 4+2n(n-1)(m-n)

=i=1n1i2×4+i=1n1×4+2n(n1)(mn)=\sum_{i=1}^{n-1}{i^2} \times 4+ \sum_{i=1}^{n-1} \times 4+2n(n-1)(m-n)

i=1ni2=n(n+1)(2n+1)6\sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}{6}

ans3=[n(n1)(2n1)6+n(n1)2]×4+2n(n1)(mn)ans_3=[\frac{n(n-1)(2n-1)}{6}+\frac{n(n-1)}{2}]\times4+2n(n-1)(m-n)

=2n(n1)(2n1)3+2n(n1)(mn)=\frac {2n(n-1)(2n-1)}{3}+2n(n-1)(m-n)

最后再把ans1ans_1ans2ans_2ans3ans_3加起来即可

Ps:此题不能通过分析边角与非边角位置的攻击数来统计答案,这样会使解答更为复杂。

评论