2020-08-19

http://icpc.upc.edu.cn/problem.php?cid=2550&pid=6

题目描述

Rainy7 一天醒来，发现自己进入了魔法世界。

一道大门矗立在 Rainy7 面前，似乎需要密码解锁。

Rainy7 经过一番查找后，找到了密码对应的问题：在n×m的棋盘上摆放两个不同颜色的皇后，使得它们能够相互攻击，总共有多少种摆法？

我们称两个皇后能够相互攻击，当且仅当它们在同一行或同一列或同一斜线上。

她只用了114514-1919810 s就解决了问题并打开了大门，于是把问题交给了您。

输入

第一行一个整数t，表示数据组数。
接下来t行，每行两个正整数n,m，表示棋盘的长和宽。

输出

t行，每行一个数，表示方案数。
由于这个数可能很大，您只要输出它对109+7取模的结果就可以了。

样例输入

【样例1】
1
2 2
【样例2】
1
114514 114514
【样例3】
2
165528 123456
132435 423153

样例输出

【样例1】
12
【样例2】
587308676
【样例3】
718509545
475373430

提示

样例1解释
如图所示：

对于20%的数据，1≤n,m≤50,1≤t≤10
对于50%的数据，1≤n,m≤300
对于70%的数据，1≤n,m≤5000
对于100%的数据，1≤n,m≤5×105,1≤t≤5000
本题部分数据卡常，请注意常数优化

解析

这道题目可以分为三种情况来讨论，横竖和对角线，横和竖都比较简单，结果为nm(n+m-2)，对角线上推到见下图：

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include 
using namespace std;
typedef long long ll;
const int mod=1e9+7;
ll n,m;
ll mul(ll a,ll b)
{
    ll sum1=0;
    ll sum2=a;
    while(b!=0)
    {
        if(b%2==1)
            sum1=(sum1+sum2)%mod;
        sum2=(sum2+sum2)%mod;
        b=b/2;
    }
    return sum1;
}
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll ans=0;
        scanf("%lld%lld",&n,&m);
        if(n>m)
            swap(n,m);
        ans+=mul(n*m,n+m-2);
        ll k1=n*(n-1)*2;
        ll k2=3*m-n-1;
        if(k1%3==0)
            k1=k1/3;
        else if(k2%3==0)
            k2=k2/3;
        ans+=mul(k1,k2);
        printf("%lldn",ans%mod);
    }
    return 0;
}