51NOD 1661 칠판 의 게임 (게임 규칙 찾기) - 알고리즘 말 라 송 17 (올림픽 과 작별)

전송 문
1661 칠판 위의 게임
Alice 와 Bob 은 칠판 에 게임 을 하 는데 칠판 에 n 개의 정수 a1, a2,..., an 이 라 고 쓰 여 있 습 니 다. 게임 의 규칙 은?
이러한:
1. 앨 리 스 가 선수권 을 가진다.
2. 모든 사람 이 1 보다 큰 숫자 를 선택 하여 지 울 수 있 고 더 작은 숫자 를 쓸 수 있 으 며 숫자 는 반드시 정 해 야 한다.
세 어 본 다음 에 상대방 이 다음 조작 을 한다.
3. 지 워 진 숫자 가 x (x > 1) 라면 x / k 보다 작 을 수 는 없 지만 x 보다 작 습 니 다.여기
나눗셈 은 유리수 나눗셈 이다.
4. 어떤 숫자 1 도 지 울 수 없습니다. 현재 숫자 하 나 를 찾 아 조작 할 수 없다 면 현재 가 져 야 합 니 다.
Alice 와 Bob 이 모두 가장 좋 은 전략 을 선택한다 고 가정 하면 Alice 에 필승 방안 이 있 습 니까?
Input
첫 번 째 줄 의 두 칸 으로 구 분 된 정수 n 과 k 는 n 은 숫자의 개 수 를 나타 내 고 k 는 게임 의 인 자 를 나타 낸다.
두 번 째 줄 n 개의 빈 칸 으로 구 분 된 정수 중 i 는 ai 를 나타 낸다.
1 ≤ n ≤ 10^5, 2 ≤ k ≤ 10^18, 1 ≤ ai ≤ 10^18。
Output
만약 에 필승 방안 이 존재 한다 면 'Alice i y' 를 출력 합 니 다. 그 중에서 i 와 y 는 선수 의 필승 을 나타 내 는 동작 입 니 다. i 를
개 수 를 y 로 수정 하 다.
없 으 면 '밥' 을 출력 하면 후수 필승 을 의미한다.(출력 에 따옴표 가 포함 되 지 않 음)
입력 예제
4 2
2 3 3 3
출력 예제
Alice 2 2
문제 풀이 방향:
공식 문제 풀이 (상세):
k 를 고정 한 후 sg (n) 에 대해 시 계 를 치면 모든 숫자 가 처음으로 나타 나 는 위치 가 매우 규칙 적 이라는 것 을 알 수 있다. 즉, 간격 이다.
몇 개의 숫자 에 이미 있 는 숫자 가 나 타 났 다.각 숫자의 첫 번 째 위 치 를 삭제 한 후 남 은 숫자 를
다시 한 열 로 배열 하면 원래 의 표 와 같은 구조 이 므 로 sg (n) 의 재 귀 해 는?
sg (1) = 0, sg (a ∗ k + 1) = sg (a), sg (a ∗ k + b) = a (k - 1) + b - 1 (1 < b < = k, b 의 정의 에 주의).
이 문 제 는 n 개 게임 의 합 이기 때문에 대응 하 는 sg 값 은 sg (a1) 입 니 다. xor sg(a2) xor ... xor sg(an)。
sg 값 이 0 이면 후수 필승.
sg 값 이 0 이 아니라면 선 수 는 반드시 이 깁 니 다. 필승 의 조작 은 다음 게임 의 sg 값 을 0 으로 바 꾸 고 현 재 를 설정 하 는 것 입 니 다.
의 sg 값 이 m 이면 i 와 y 를 찾 아서 m = sg (ai) xor sg(y) ，
그러면 sg (y) = m xor sg (ai, p = m 설정 가능 xor sg (ai), q = (p - 1) / (k - 1) ∗ k + (p - 1) (p = 0 시 특 판 q = 1),
가능 한 y 는 q, qk + 1, (qk + 1) k + 1 뿐 입 니 다. 그 중에서 ai 보다 작은 것 은 O (logk (ai) 개 뿐 입 니 다.
그 중에서 ai / k 보다 작 지 않 은 것 을 찾 으 면 됩 니 다. 매 거 i 는 i 에 대응 하 는 실행 가능 한 y 를 찾 을 수 있 습 니 다.
위로 추출 하고 정수 가 넘 치 는 것 을 판단 하 세 요.
여기 서 간단 한 증명 을 추가 합 니 다. sg 함수 의 정 의 를 바탕 으로 한 국면 의 sg 값 은 그 후계 국면 의 sg 값 과 같 습 니 다.
안에 나타 나 지 않 은 가장 작은 비 마이너스 정수, 예 를 들 어 본 문 제 는 sg (n) = mex (sg (n - 1), sg (n - 2), sg (n - 1) / k + 1) 이다.
그 중에서 mex (S) 는 집합 S 에 나타 나 지 않 은 최소 비 마이너스 정 수 를 나타 내 고 나 누 기 는 아래 에서 정 리 된 정수 나 누 기 이다.
n 과 n - 1 을 고려 하면 이들 이 대응 하 는 후계 집합 은 최대 두 가지 요소 가 다 르 기 때문에 수학 귀납법 을 이용 하여 나 누 려 고 한다.
sg (n) 를 분석 할 때 sg (1), sg (2), sg (n - 1) 를 얻 었 다 고 가정 하면 상기 결론 을 만족 시 킬 수 있다.
후계 국면 은 한 구간 의 형식 으로 쓸 수 있 기 때문에 아래 의 분석 은 [L, R] 로 간략화 하여 표시 한다.
(sg(L),sg(L+1),...,sg(R))
n = ak + 1 시 ak + 1 에 대응 하 는 후 계 는 [a + 1, ak] 이 고 ak 에 대응 하 는 후 계 는 [a, ak - 1] 이다.
sg (ak + 1) ≠ sg (a) 를 가정 하면 sg (ak + 1) < sg (a) 는 a 가 ak + 1 의 후 가 아니 기 때문이다.
이 어 sg (a) 가 최소 로 나타 나 지 않 은 것 이 아니라면 최소 로 나타 나 지 않 은 것 은 더 작은 숫자 일 수 밖 에 없다.
sg (ak + 1) 는 sg (a) 보다 작은 숫자 이기 때문에 [a + 1, ak] 에 이 숫자 가 없다 는 것 을 설명 합 니 다. 그러면
[a, ak − 1] 에 서 는 이 수가 없 기 때문에 sg (ak) < = sg (ak + 1), 따라서 sg (ak) < sg (a)
그러나 sg (ak) 는 귀납 적 가설 에 따라 [1, ak] 에서 가장 큰 값 이기 때문에 sg (a) < = sg (ak) 와 위 가 있다.
서술 에 모순 이 생 겼 기 때문에 sg (ak + 1) = sg (a)
n = ak + b (1 < b < = k) 시 n 에 대응 하 는 후 계 는 [a + 1, n - 1], n - 1 에 대응 하 는 것 이다.
다음은 [a + 1, n - 2].
위 에서 알 수 있 듯 이 sg (n - 1) < sg (n) 는 sg (n - 1) 가 n - 1 의 후계 리 에 없 기 때문이다.
나타 나 기 때문에 sg (n) 는 커지 기만 하고 작 아 지지 않 습 니 다.
만약 b = 2, 그러면 sg (n - 1) = sg (a) 는 n 의 후계 가 [a, ak] 에 해당 하고 귀납 적 가설 에 따른다.
이 안의 값 은 모두 0 에서 sg (ak) 사이 이기 때문에 sg (n) = sg (n - 2) + 1 이다.
b > 2 라면 같은 이치 로 sg (n) = sg (n - 1) + 1 을 얻 을 수 있 습 니 다.
그리고 구체 적 인 식 을 찾 으 면 됩 니 다. 구체 적 인 식 이 있 으 면 역 매 핑 을 쉽게 찾 을 수 있 습 니 다.
많은 세부 적 인 문제 에 주의해 야 한다. Code：

/**
2016 - 08 - 29   
Author: ITAK

Motto:

           ，           ，
            ，       。
**/

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const LL INF = 1e18+5;
const int MAXN = 1e6+5;
const LL MOD = 1e9+7;
const double eps = 1e-7;
const double PI = acos(-1);
using namespace std;
LL Scan_LL()///    
{
    LL res=0,ch,flag=0;
    if((ch=getchar())=='-')
        flag=1;
    else if(ch>='0'&&ch<='9')
        res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+ch-'0';
    return flag?-res:res;
}
int Scan_Int()///    
{
    int res=0,ch,flag=0;
    if((ch=getchar())=='-')
        flag=1;
    else if(ch>='0'&&ch<='9')
        res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        res=res*10+ch-'0';
    return flag?-res:res;
}
void Out(LL a)///    
{
    if(a>9)
        Out(a/10);
    putchar(a%10+'0');
}
LL a[MAXN], sg[MAXN];
int main()
{
    int n;
    LL k;
    while(~scanf("%d%lld",&n,&k))
    {
        LL ans = 0, tmp, ret, x;
        int j = -1;
        memset(a, 0, sizeof(a));
        for(int i=1; i<=n; i++)
        {
            x = Scan_LL();
            a[i] = x;
            if(x == 1)
                continue;
            tmp = x;
            LL tp1 = x/k;
            LL tp2 = x%k;
            while(tmp)
            {
                if(tp2 == 0)
                {
                    tp1--;
                    tp2 = k;
                    sg[i] = (tp1*(k-1)+tp2-1);
                    ///cout<
                    ans ^= sg[i];
                    break;
                }
                else if(tp2 > 1)
                {
                    sg[i] = (tp1*(k-1)+tp2-1);
                    ans ^= sg[i];
                    break;
                }
                else
                {
                    tmp = (tmp-1)/k;
                    tp1 = tmp/k;
                    tp2 = tmp%k;
                }
            }
        }
        if(ans)
        {
            tmp = ans;
            for(int i=1; i<=n; i++)
            {
                if(a[i] == 1)
                    continue;
                LL p = (tmp ^ sg[i]);
                LL q = (p-1)/(k-1)*k+(p-1)%(k-1)+2;
                if(p == 0)
                    q = 1;
                ret = q;
                while(1)
                {
                    if(ret>=a[i] || ret<0)
                        break;
                    LL tp = a[i]/k;
                    if(a[i] % k)
                        tp++;
                    if(ret >= tp)
                    {
                        j = i;
                        goto endW;
                    }
                    ret = ret*k+1;
                }
            }
            endW:;
            printf("Alice %d %lld
",j, ret);
        }
        else
            puts("Bob");
    }
    return 0;
}