题目大概说给一张地图，地图每个格子都有0到9中的某一个数字。现在要在一个格子放炸弹，炸弹爆炸后水柱有两种扩展方式，一种是上、下、左、右，另一种是左上、右下、右上、左下，且四个方向的长度都一样。问放哪个格子怎么爆炸使得水柱覆盖的格子上的数字乘积最大，结果模1e9+7。
这题不会做。。
- 首先，各个格子的值取对数，这个为了比大小，因为需要模数，通过取对数缩小值。另外也把乘法转化成加法。这是个挺经典的技巧。
- 接下来，水柱的话肯定不能延长到0，不然功亏一篑，那么利用DP求出各个格子向8各个方向能延长多长，即dp[dir][x][y]。转移就是格子(x,y)不为0，从dp[dir][x+d[dir]][y+d[dir]]+1这儿转移，否则值为0。具体我是用记忆话搜索实现的。
- 然后知道各个格子8个方向能延长最长长度，上、下、左、右四个方向能够延长的最小值就是第一种水柱的拓展最优的长度，而左上、右下、右上、左下四个方向的最小值就是第二种了。
- 如何快速得出各个方向水柱覆盖的数字和——利用前缀和！这也是个挺经典的技巧。而取对数把乘法转化成加法，这就使得能利用前缀和的差求区间和。那么预处理出各个方向的前缀和就能在O(1)得出区间和了，即水柱覆盖到的格子的和。
- 最后就是通过枚举每个格子，得到各个格子放炸弹最多能得到的数字和，更新答案。
注意最后的答案不要直接求次幂还原。。会有精度问题。。应该要记录下来，在原地图中把各个数字累乘出答案。。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; int n;
double a[][];
int b[][];
//上、下、右、左、左上、右下、右上、左下
int dx[]={-,,,,-,,-,};
int dy[]={,,,-,-,,,-}; int d[][][];
int dp(int dir,int x,int y){
if(a[x][y]<) return d[dir][x][y]=;
if(d[dir][x][y]!=-) return d[dir][x][y];
int nx=x+dx[dir],ny=y+dy[dir],res=;
if(nx>= && nx<=n && ny>= && ny<=n) res+=dp(dir,nx,ny);
return d[dir][x][y]=res;
} double sum[][][];
int rec1[][],rec2[][]; int main(){
scanf("%d",&n);
for(int i=; i<=n; ++i){
for(int j=; j<=n; ++j){
scanf("%1d",&b[i][j]);
if(b[i][j]==) a[i][j]=-;
else a[i][j]=log2(b[i][j]);
}
}
for(int i=; i<=n; ++i){
for(int j=; j<=n; ++j){
sum[][i][j]=sum[][i][j-]+a[j][i];
}
}
for(int i=; i<=n; ++i){
for(int j=; j<=n; ++j){
sum[][i][j]=sum[][i][j-]+a[i][j];
}
}
for(int i=n; i>=; --i){
int x=i,y=;
for(int j=; j<=n-i+; ++j){
sum[][n-i+][j]=sum[][n-i+][j-]+a[x][y];
rec1[x][y]=j;
++x; ++y;
}
}
for(int i=; i<=n; ++i){
int x=,y=i;
for(int j=; j<=n-i+; ++j){
sum[][n+i-][j]=sum[][n+i-][j-]+a[x][y];
rec1[x][y]=j;
++x; ++y;
}
}
for(int i=; i<=n; ++i){
int x=,y=i;
for(int j=; j<=i; ++j){
sum[][i][j]=sum[][i][j-]+a[x][y];
rec2[x][y]=j;
++x; --y;
}
}
for(int i=; i<=n; ++i){
int x=i,y=n;
for(int j=; j<=n-i+; ++j){
sum[][n+i-][j]=sum[][n+i-][j-]+a[x][y];
rec2[x][y]=j;
++x; --y;
}
}
memset(d,-,sizeof(d));
for(int k=; k<; ++k){
for(int i=; i<=n; ++i){
for(int j=; j<=n; ++j){
dp(k,i,j);
}
}
}
double ans=-;
int ansx,ansy,ansdir=-,anslen;
for(int i=; i<=n; ++i){
for(int j=; j<=n; ++j){
if(a[i][j]<) continue; int len=min(min(d[][i][j],d[][i][j]),min(d[][i][j],d[][i][j]));
double res=;
res+=sum[][j][i]-sum[][j][i-len];
res+=sum[][j][i+len-]-sum[][j][i];
res+=sum[][i][j-]-sum[][i][j-len];
res+=sum[][i][j+len-]-sum[][i][j];
if(ans<res){
ans=res;
ansx=i; ansy=j; ansdir=; anslen=len;
} len=min(min(d[][i][j],d[][i][j]),min(d[][i][j],d[][i][j]));
res=;
res+=sum[][n-i+j][rec1[i][j]]-sum[][n-i+j][rec1[i][j]-len];
res+=sum[][n-i+j][rec1[i][j]+len-]-sum[][n-i+j][rec1[i][j]];
res+=sum[][i+j-][rec2[i][j]-]-sum[][i+j-][rec2[i][j]-len];
res+=sum[][i+j-][rec2[i][j]+len-]-sum[][i+j-][rec2[i][j]];
if(ans<res){
ans=res;
ansx=i; ansy=j; ansdir=; anslen=len;
}
}
}
if(ansdir==-){
printf("");
return ;
}
long long res=;
if(ansdir==){
for(int i=ansx-anslen+; i<=ansx+anslen-; ++i){
res*=b[i][ansy];
res%=;
}
for(int i=ansy-anslen+; i<=ansy+anslen-; ++i){
if(i==ansy) continue;
res*=b[ansx][i];
res%=;
}
}else{
int x=ansx-anslen+,y=ansy-anslen+;
for(int i=; i<anslen*; ++i){
res*=b[x][y];
res%=;
++x; ++y;
}
x=ansx-anslen+; y=ansy+anslen-;
for(int i=; i<anslen*; ++i){
if(x==ansx && y==ansy){
++x; --y;
continue;
}
res*=b[x][y];
res%=;
++x; --y;
}
}
printf("%lld",res);
return ;
}