ZR#955 折纸

ZR#955 折纸

解法:

CODE:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

#define LL long long

const int N = 2e6 + 50;

char s[N],tt[N];

string p[N];

int HL[N],WL[N],m,n;

int HR[N],WR[N],t[N],f[N];

int manacher(int *p, char *ss, int Len) {

	int len = 0; s[0] = '(';

	for(int i = 1 ; i <= Len ; ++ i) {

		s[++ len] = '#';

		s[++ len] = ss[i];

	}

	s[++ len] = '#', s[++ len] = ')';

	int mx = 0, id = 0;

	for(int i = 1 ; i < len ; ++ i) {

		if(i < mx) p[i] = min(mx - i, p[2 * id - i]);

		else p[i] = 1;

		while(s[i + p[i]] == s[i - p[i]]) ++ p[i];

		if(i + p[i] > mx) mx = i + p[i], id = i;

	}

	return len;

}

int main() {

	scanf("%d%d",&n,&m);

    for(int i = 1 ; i < n  ; i++)

        HL[i] = HR[i] = 1;

    for(int i = 1 ; i < m ; i++)

        WL[i] = WR[i] = 1;

	for(int i = 1 ; i <= n ; i++)

        cin >> p[i];

	for(int i = 1 ; i <= n ; i++) {

		int len = m;

		for(int j = 1 ; j <= len ; j++)

            tt[j] = p[i][j - 1];

		int Len = manacher(t, tt, m) - 3;

		int mx = 1;

		for(int j = 3 ; j <= Len ; j += 2) {

			if(j - t[j] + 1 <= mx) mx = j;

			else WL[j >> 1] = 0;

		}

		int mn = Len + 2;

		for(int j = Len ; j >= 3 ; j -= 2) {

			if(j + t[j] - 1 >= mn) mn = j;

			else WR[j >> 1] = 0;

		}

	}

	LL ansW = 0;

	int sum = 0;

	WL[0] = 1, WR[m] = 1;

    for(int i = 0 ; i <= m ; i++) sum += WR[i];

	for(int i = 0 ; i <= m ; i++) {

		if(WR[i]) -- sum;

		if(WL[i]) ansW += sum;

	}

	swap(n, m);

	for(int i = 1 ; i <= n ; i++) {

		int len = m;

		for(int j = 1 ; j <= len ; j++)

            tt[j] = p[j][i - 1];

		int Len = manacher(t, tt, m) - 3;

		int mx = 1;

		for(int j = 3 ; j <= Len ; j += 2) {

			if(j - t[j] + 1 <= mx) mx = j;

			else HL[j >> 1] = 0;

		}

		int mn = Len + 2;

		for(int j = Len ; j >= 3 ; j -= 2) {

			if(j + t[j] - 1 >= mn) mn = j;

			else HR[j >> 1] = 0;

		}

	}

	LL ansH = 0;

	sum = 0;

	HL[0] = 1, HR[m] = 1;

	for(int i = 0 ; i <= m ; i++) sum += HR[i];

	for(int i = 0 ; i <= m ; i++) {

		if(HR[i]) -- sum;

		if(HL[i]) ansH += sum;

	}

	printf("%lld\n", ansW * ansH);

    //system("pause");

    return 0;

}