laekov

解锁成就：半夜过题。（其实是因为在搞bsd）

仔细看下题推一下发现第n维中m维元素的个数为2^(n-m)*C(n,m)。

然后组合数好像得nlogn用逆元？恭喜tle。

然后yy了一个用线性筛的办法，只是素数用快速幂，这样大约可以降低复杂度，然后就能过了。好神奇。

代码好长TT。

#include <cstdio>

#include <cstring>

#define _l (long long int)

const int maxn = 10000009;

int tp, pn[maxn], inv[maxn];

bool pr[maxn];

int n, mod, s, c, p;

int modPow(int a, int x) {

    int s = 1;

    for (; x; x >>= 1, a = _l a * a % mod)

        if (x & 1)

            s = _l s * a % mod;

    return s;

}

void pre(int n) {

memset(pr, 0, sizeof(pr));

inv[1] = 1;

tp = 0;

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

if (!pr[i]) {

pn[tp ++] = i;

inv[i] = modPow(i, mod - 2);

}

for (int j = 0; j < tp && i * pn[j] <= n; ++ j) {

pr[i * pn[j]] = 1;

inv[i * pn[j]] = _l inv[i] * inv[pn[j]] % mod;

if (i % pn[j] == 0)

break;

}

}

}

int main() {

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

pre(n);

c = 1;

p = 1;

s = 0;

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

s ^= _l c * p % mod;

p = p * 2 % mod;

c = _l c * inv[i + 1] % mod * (n - i) % mod;

}

printf("%d\n", s);

}

upd: mhy大神出了组数据把我卡掉了。结果是n>mod的时候要考虑mod的倍数的问题。好厉害orz