BZOJ1223 [HNOI2002]Kathy函数

比较神奇的数学题。首先你要知道这个函数的意思是把它的二进制flip。至于怎么来的我也是听说的。然后推一下发现的确是这么回事。

于是就变成数位dp了。然后我发现数位dp常常可以用奇奇怪怪的方法水过去。然后又发现数组从0开始标号也会造成麻烦。+1-1啥的最讨厌了。

于是这题就变成高精度练习题了。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 409;

struct BigInt {
	int l, a[maxn], base;
	BigInt(int b = 10) {
		l = 0;
		base = b;
	}
	void push() {
		for (int i = 0; i < l - 1; ++ i) {
			a[i + 1] += a[i] / base;
			a[i] %= base;
		}
		for (; a[l - 1] >= base; ++ l) {
			a[l] = a[l - 1] / base;
			a[l - 1] %= base;
		}
	}
	void pull() {
		for (; l && !a[l - 1]; -- l);
	}
	void read() {
		static char g[maxn];
		base = 10;
		scanf("%s", g);
		l = strlen(g);
		for (int i = 0; i < l; ++ i)
			a[i] = g[l - i - 1] - 48;
		pull();
	}

	inline void setOne() {
		l = 1;
		a[0] = 1;
	}
	inline void setZero() {
		l = 0;
	}

	void assAdd(const BigInt& x) {
		for (int i = 0; i < l && i < x. l; ++ i)
			a[i] += x. a[i];
		for (int i = l; i < x. l; ++ i)
			a[i] = x. a[i];
		if (x. l > l)
			l = x. l;
		push();
	}
	void assDec() {
		-- a[0];
		for (int i = 0; a[i] < 0; ++ i) {
			a[i] += base;
			-- a[i + 1];
		}
		pull();
	}
	void assMul(int x) {
		for (int i = 0; i < l; ++ i)
			a[i] *= x;
		push();
	}
	int mod(int x) const {
		int s(0);
		for (int i = l - 1; i >= 0; -- i)
			s = (s * base + a[i]) % x;
		return s;
	}
	void assDiv(int x) {
		for (int i = l - 1; i >= 0; -- i) {
			if (i)
				a[i - 1] += a[i] % x * base;
			a[i] /= x;
		}
		pull();
	}
	int compareTo(const BigInt& x) const {
		if (l > x. l)
			return 1;
		else if (l < x. l)
			return -1;
		for (int i = l - 1; i >= 0; -- i)
			if (a[i] > x. a[i])
				return 1;
			else if (a[i] < x. a[i])
				return -1;
		return 0;
	}
	void ass(const BigInt& x) {
		static BigInt tmp;
		if (base == x. base) {
			l = x. l;
			memcpy(a, x. a, sizeof(a));
		}
		else {
			tmp. base = x. base;
			tmp. ass(x);
			for (l = 0; tmp. l; ++ l) {
				a[l] = tmp. mod(base);
				tmp. assDiv(base);
			}
		}
	}
	void print(char eon = 10) {
		for (int i = l - 1; i >= 0; -- i)
			putchar(a[i] + 48);
		if (!l)
			putchar(48);
		if (eon)
			putchar(eon);
	}
	void flip() {
		for (int i = 0; (i << 1) < l; ++ i)
			swap(a[i], a[l - i - 1]);
		pull();
	}
};

BigInt tmp, m, bm(2), br(2), ans, p2[maxn], ONE;

bool checkFlip(const BigInt& a) {
	int q(a. l >> 1), p(a. l - q - 1);
	for (int i = 0; p - i >= 0; ++ i)
		if (a. a[p - i] > a. a[q + i])
			return 1;
		else if (a. a[p - i] < a. a[q + i])
			return 0;
	return 1;
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
#endif

	ONE. setOne();
	tmp. read();
	m. ass(tmp);
	bm. ass(tmp);
	int l((bm. l + 1) >> 1);
	p2[0]. setOne();
	for (int i = 1; i <= l; ++ i) {
		p2[i]. ass(p2[i - 1]);
		p2[i]. assMul(2);
	}
	for (int i = 1; i < bm. l; ++ i)
		ans. assAdd(p2[((i + 1) >> 1) - 1]);
	for (int i = bm. l - 2; i > bm. l - l - 1; -- i)
		if (bm. a[i])
			ans. assAdd(p2[i - (bm. l >> 1)]);
	if (checkFlip(bm))
		ans. assAdd(ONE);
	ans. print();
}