第一条题解

#include<bits/stdc++.h>
using namespace std;
#define MAXN 305
#define LL long long
#define ULL unsigned long long
#define ENDL putchar('\n')
#define DB double
#define lowbit(x) (-(x) & (x))
#define FI first
#define SE second
#define PR pair<int,int>
#define UIN unsigned int
int xchar() {
	static const int maxn = 1000000;
	static char b[maxn];
	static int pos = 0,len = 0;
	if(pos == len) pos = 0,len = fread(b,1,maxn,stdin);
	if(pos == len) return -1;
	return b[pos ++];
}
// #define getchar() xchar()
inline LL read() {
	LL f = 1,x = 0;int s = getchar();
	while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
	while(s >= '0' && s <= '9') {x = (x<<1) + (x<<3) + (s^48);s = getchar();}
	return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar((x%10)^48);}
inline void putnum(LL x) {
	if(!x) {putchar('0');return ;}
	if(x<0) putchar('-'),x = -x;
	return putpos(x);
}
inline void AIput(LL x,int c) {putnum(x);putchar(c);}

int n,m,s,o,k;
char a[305][305];
int vc[605][305],cn[605];
int l[605][605],r[605][605];
int main() {
	n = read();
	for(int i = 1;i <= n;i ++) {
		scanf("%s",a[i] + 1);
		for(int j = 1;j <= n;j ++) {
			if(a[i][j] == '*') {
				vc[i-j+n][++ cn[i-j+n]] = i+j;
			}
		}
	}
	for(int i = 1;i <= n+n;i ++) {
		vc[i][++ cn[i]] = n+n+1;
		for(int j = 1;j <= cn[i];j ++) {
			int ll = (j==1 ? 1:vc[i][j-1]),rr = vc[i][j];
			l[i][rr] = j; r[i][ll] = j-1;
			for(int k = ll+1;k < rr;k ++) {
				l[i][k] = j; r[i][k] = j-1;
			}
		}
	}
	LL ans = 0;
	for(int i = 1;i <= n;i ++) {
		for(int j = 1;j <= n;j ++) {
			if(a[i][j] == '*') {
				int x = i+1,y = j+1,d = 2,ii = i-j+n;
				while(x <= n && y <= n) {
					if(a[x][y] == '*') {
						int ll,rr;
						if(ii > d) {
							ll = l[ii-d][i+j],rr = r[ii-d][x+y];
							if(ll <= rr) ans += rr-ll+1;
						}
						if(ii + d <= n+n) {
							ll = l[ii+d][i+j],rr = r[ii+d][x+y];
							if(ll <= rr) ans += rr-ll+1;
						}
					}
					x ++; y ++; d += 2;
				}
			}
		}
	}
	for(int i = 1;i <= n+n;i ++) cn[i] = 0;
	for(int i = 1;i <= n;i ++) {
		for(int j = 1;j+j <= n;j ++) swap(a[i][j],a[i][n-j+1]);
		for(int j = 1;j <= n;j ++) {
			if(a[i][j] == '*') {
				vc[i-j+n][++ cn[i-j+n]] = i+j;
			}
		}
	}
	for(int i = 1;i <= n+n;i ++) {
		vc[i][++ cn[i]] = n+n+1;
		for(int j = 1;j <= cn[i];j ++) {
			int ll = (j==1 ? 1:vc[i][j-1]),rr = vc[i][j];
			l[i][rr] = j; r[i][ll] = j-1;
			for(int k = ll+1;k < rr;k ++) {
				l[i][k] = j; r[i][k] = j-1;
			}
		}
	}
	for(int i = 1;i <= n;i ++) {
		for(int j = 1;j <= n;j ++) {
			if(a[i][j] == '*') {
				int x = i+1,y = j+1,d = 2,ii = i-j+n;
				while(x <= n && y <= n) {
					if(a[x][y] == '*') {
						int ll,rr;
						if(ii > d) {
							ll = l[ii-d][i+j+1],rr = r[ii-d][x+y-1];
							if(ll <= rr) ans += rr-ll+1;
						}
						if(ii + d <= n+n) {
							ll = l[ii+d][i+j+1],rr = r[ii+d][x+y-1];
							if(ll <= rr) ans += rr-ll+1;
						}
					}
					x ++; y ++; d += 2;
				}
			}
		}
	}
	AIput(ans,'\n');
	return 0;
}