题解：CF677E Vanya and Balloons
Unaccepted_Zhou
·
·
题解
:::info[思路]
显然考虑十字中心，对于 $2\times4$ 个方向取到最后一个非 $0$，前缀和统计 $2$ 和 $3$。
但我们需要比较大小。考虑经典 trick，取对数。
具体的，将 $2^a3^b$ 转化为 $a+\log_2{3}\times b$，使用 `log2()` 库函数。
:::
因为分讨很烦，我们考虑找到八个方向的通用算法。
- 使用类似二维中 dfs 使用的方向数组，避免分讨。
```cpp
ll d[8][2]={{-1,0},{1,0},{0,-1},{0,1},
{-1,-1},{1,1},{-1,1},{1,-1}};
```
- 把最近 $0$ 的 $x$ 和 $y$ 不管哪个方向的全记上，取 $x$ 和 $y$ 差值的 $\max$ 即可，方向不用管。
- $2$ 和 $3$ 直接记录 $8$ 个方向的前缀和即可，不用记 $4$ 个方向再分讨。
抛去十字中心。特判所有数都是 $0$。
:::success[code]
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e3+10,p=1e9+7;
ll d[8][2]={{-1,0},{1,0},{0,-1},{0,1},
{-1,-1},{1,1},{-1,1},{1,-1}},x[N][N][8];
ll y[N][N][8],a[N][N][8],b[N][N][8];
char s[N][N]; ll n,_a,_b,g;
void f(ll i,ll j,ll k){
ll I=i+d[k][0],J=j+d[k][1];
a[i][j][k]=a[I][J][k]+(s[i][j]=='2');
b[i][j][k]=b[I][J][k]+(s[i][j]=='3');
if(s[i][j]!='0')//==
x[i][j][k]=x[I][J][k],y[i][j][k]=y[I][J][k];
}
int main(){
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%s",s[i]+1);
for(ll i=0;i<=n+1;i++) for(ll j=0;j<=n+1;j++)
for(ll k=0;k<8;k++) x[i][j][k]=i,y[i][j][k]=j;
for(ll i=1;i<=n;i++) for(ll j=1;j<=n;j++)
for(ll k=0;k<8;k+=2) f(i,j,k);
for(ll i=n;i;i--) for(ll j=n;j;j--){
for(ll k=1;k<8;k+=2) f(i,j,k);
for(ll l=0;l<8;l+=4){
ll t=n,A=0,B=0;
for(ll k=l;k<l+4;k++)
t=min(t,max(abs(i-x[i][j][k]),abs(j-y[i][j][k])));
for(ll k=l;k<l+4;k++){
ll I=i+t*d[k][0],J=j+t*d[k][1];
A+=a[i][j][k]-a[I][J][k];
B+=b[i][j][k]-b[I][J][k];
}
if(s[i][j]=='0') continue; g=1;//`
if(s[i][j]=='2') A-=3; if(s[i][j]=='3') B-=3;//`
long double s=log2(3)*B+A,S=log2(3)*_b+_a;
if(s>S) _a=A,_b=B;
}
}
n=1; while(_a--) n=n*2%p; while(_b--) n=n*3%p;//-
printf("%lld",g*n);
return 0;
}
```
:::
~~模数打成 $998244353$ WA 了。~~