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

 

于是就变成数位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&amp; x) {
	for (int i = 0; i &lt; l &amp;&amp; i &lt; x. l; ++ i)
		a[i] += x. a[i];
	for (int i = l; i &lt; x. l; ++ i)
		a[i] = x. a[i];
	if (x. l &gt; l)
		l = x. l;
	push();
}
void assDec() {
	-- a[0];
	for (int i = 0; a[i] &lt; 0; ++ i) {
		a[i] += base;
		-- a[i + 1];
	}
	pull();
}
void assMul(int x) {
	for (int i = 0; i &lt; l; ++ i)
		a[i] *= x;
	push();
}
int mod(int x) const {
	int s(0);
	for (int i = l - 1; i &gt;= 0; -- i)
		s = (s * base + a[i]) % x;
	return s;
}
void assDiv(int x) {
	for (int i = l - 1; i &gt;= 0; -- i) {
		if (i)
			a[i - 1] += a[i] % x * base;
		a[i] /= x;
	}
	pull();
}
int compareTo(const BigInt&amp; x) const {
	if (l &gt; x. l)
		return 1;
	else if (l &lt; x. l)
		return -1;
	for (int i = l - 1; i &gt;= 0; -- i)
		if (a[i] &gt; x. a[i])
			return 1;
		else if (a[i] &lt; x. a[i])
			return -1;
	return 0;
}
void ass(const BigInt&amp; 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 &gt;= 0; -- i)
		putchar(a[i] + 48);
	if (!l)
		putchar(48);
	if (eon)
		putchar(eon);
}
void flip() {
	for (int i = 0; (i &lt;&lt; 1) &lt; 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) &gt;&gt; 1);
p2[0]. setOne();
for (int i = 1; i &lt;= l; ++ i) {
	p2[i]. ass(p2[i - 1]);
	p2[i]. assMul(2);
}
for (int i = 1; i &lt; bm. l; ++ i)
	ans. assAdd(p2[((i + 1) &gt;&gt; 1) - 1]);
for (int i = bm. l - 2; i &gt; bm. l - l - 1; -- i)
	if (bm. a[i])
		ans. assAdd(p2[i - (bm. l &gt;&gt; 1)]);
if (checkFlip(bm))
	ans. assAdd(ONE);
ans. print();



}