[ICPC2020 Nanjing R] Harmonious Rectangle 题解

· · 题解

题解来源于一位和我组队且不愿透露姓名的好兄弟。

这个题有点类似于 2018 年考过的填数游戏。

首先考虑正难则反，也即考虑有多少染色不存在这样的子矩形。注意到，这样的子矩形的特征是两个同色格子在一行或者一列，另两个同色格子在一行或者一列。

所以，这样的矩阵必然满足，对于同行的两个同色格子，这两行其他列的对应位置两个格子必然不一样，列同理。

于是我们直接考虑某一行一种颜色的鸽子就好了，显然一行的某种颜色的格子不可能超过四个，由抽屉原理可以知道，必然在其他行会存在一个同色对，于是一行同色格子最多三个。然而只给了红黄蓝三种颜色，再用一次抽屉原理，当矩形的长或宽超过 10 的时候，必然存在一种颜色出现超过 4 次。由此分析，矩形的长和宽最多为 9。

然后写个爆搜就好了。不要认为最多可能状态有 3^{81} 种，首先你可以剪枝，其次你在搜完之后就会发现有值时对应的 n 和 m 非常少，打个表就能过了。

记得特判 n=1 或者 m=1 的情况。

代码

#include<bits/stdc++.h>
using namespace  std;
typedef int ll;
typedef long long int li;
const ll MAXN=3e5+51,MOD=1e9+7;
ll test,n,m,res;
ll c[15][15];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();       
    }
    return num*neg;
}
inline ll qpow(ll base,ll exponent)
{
    ll res=1;
    while(exponent)
    {
        if(exponent&1)
        {
            res=(li)res*base%MOD;
        }
        base=(li)base*base%MOD,exponent>>=1;
    }
    return res;
}
inline void solve()
{
    n=read(),m=read(),n>m?swap(n,m):(void)1;
    if(n==1||m==1)
    {
        return (void)puts("0");
    }
    if(n>=8||m>=8)
    {
        return (void)printf("%d\n",qpow(3,n*m));
    }
    printf("%d\n",(qpow(3,n*m)-c[n][m]+MOD)%MOD);
}
int main()
{
    test=read();
    c[2][2]=66,c[2][3]=390,c[2][4]=1800,c[2][5]=6120,c[2][6]=13680,c[2][7]=15120;
    c[3][3]=3198,c[3][4]=13176,c[3][5]=27000,c[3][6]=13680,c[3][7]=15120;
    c[4][4]=24336,c[4][5]=c[5][5]=4320;
    for(register int i=1;i<=test;i++)
    {
        solve();    
    }
}