DDOSvoid's Blog

CF 850C Arpa and a game with Mojtaba

发表于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

题目描述

https://codeforces.com/contest/850/problem/C

Solution

首先能够发现可以根据素数分成不同的子游戏，最后只需要将 $SG$ 值异或即可

我们考虑其中一个游戏，注意到相同的数字没有用，并且数字的上界是 $30$，所以直接状态压缩一下

然后暴力枚举转移计算 $SG$ 值即可，可以大胆猜测状态会非常少

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
34
35
36
37
38
39
40
41
42
43
44
#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#include <vector>
#include <set>
#define maxn 110
using namespace std;

int n, a[maxn], mx;

const int N = 30;
map<int, int> f;
int dp(int n) {
    if (f.find(n) != f.end()) return f[n]; vector<int> mex(N + 10);
    for (int i = 1; i <= N; ++i) {
        if (!(n >> i)) break; 
        mex[dp(n >> i | n & (1 << i) - 1)] = 1; 
    }
    for (int i = 0; i < N + 10; ++i)
        if (!mex[i]) return f[n] = i; 
}

int ans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    cin >> n; f[0] = f[1] = 0;
    for (int i = 1; i <= n; ++i) cin >> a[i], mx = max(mx, a[i]); 
    for (int i = 2; i * i <= mx; ++i) {
        int S = 1;
        for (int j = 1; j <= n; ++j) {
            int s = 0;
            while (a[j] % i == 0) a[j] /= i, ++s;
            S |= 1 << s;
        }
        ans ^= dp(S); 
    } sort(a + 1, a + n + 1); int cnt = unique(a + 1, a + n + 1) - a - 1; 
    for (int i = 1; i <= cnt; ++i) if (a[i] > 1) ans ^= 1; 
    cout << (!ans ? "Arpa\n" : "Mojtaba\n"); 
    return 0;
}