QBPAL - Đếm chuỗi đối xứng

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int BASE = 1000000000, MAX_DIGIT = 5, LOG_BASE = 9, N = 120;
struct BigInteger {
	int d[MAX_DIGIT], n;

	void operator = (const int &x) {
		memset(d, 0, sizeof d); n = 0;
		for(int t = x; t != 0; t /= BASE)
			d[n++] = t % BASE;
	}

	void operator += (const BigInteger &a) {
		int rem = 0; n = max(n, a.n);
		for(int i = 0; i < n; ++i) {
			int p = d[i] + a.d[i] + rem;
			if(p >= BASE) d[i] = p - BASE, rem = 1;
			else d[i] = p, rem = 0;
		}
		if(rem) d[n++] = rem;
	}

	void operator -= (const BigInteger &a) {
		int rem = 0;
		for(int i = 0; i < n; ++i) {
			int p = d[i] - a.d[i] - rem;
			if(p < 0) d[i] = p + BASE, rem = 1;
			else d[i] = p, rem = 0;
		}
		while(n > 0 && d[n-1] == 0) --n;
	}

	void print() {
		printf("%d", d[n-1]);
		for(int i = n-2; i >= 0; --i)
			printf("%0*d", LOG_BASE, d[i]);
		printf("\n");
	}
} f[N][N], ONE;
char s[N+1];

int main() {
	ONE = 1; scanf("%s", s); int n = strlen(s);
	for(int i = 0; i < n; ++i) f[i][i] = ONE;
	for(int l = 2; l <= n; ++l)
		for(int i = 0, j = l - 1; j < n; ++i, ++j) {
			f[i][j] = f[i+1][j];
			f[i][j] += f[i][j-1];
			if(s[i] == s[j]) f[i][j] += ONE;
			else f[i][j] -= f[i+1][j-1];
		}
	f[0][n-1].print();
	return 0;
}

Download