LuoguU14474 - [NOIP 模拟赛 by WISCO] 答案错误

2017/10/29

题目

让人窒息的题面,而且我还不会翻译。

考虑多项式

中的所有数划分成两个大小相等的集合,使得不论 a 取何值,两集合中各元素带入 多项式之后的和相等。

有 m 组询问,每次询问一个数在第一个集合中,还是在第二个集合中。

n <= 60, m <= 1e6

解法

数据范围提示倍增

再看看样例

1 2 3 4 5 6 7 8

划分为

1 4 6 7

2 3 5 8

猜测倍增后高位的答案是低位取反

写个程序验证一下就好

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

int N, M;

int check(long long x) {
    int ret = 0;
#ifdef __GNUC__
    ret = __builtin_parityll(x);
#else
    int ret = 0;
    while(x) {
        ret++;
        x -= (x) & (-x);
    }
    ret = ret & 1;
#endif

    return ret;
}

int main() {
    scanf("%d %d", &N, &M);

    long long x;
    while(M--) {
        scanf("%lld", &x); x--;
        puts(check(x) ? "Z" : "X");
    }
}