zoj3591 Nim---비트 연산 바둑
Time Limit: 3 Seconds
Memory Limit: 65536 KB
Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. The game ends when one of the players is unable to remove object in his/her turn. This player will then lose. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap. Here is another version of Nim game. There areN piles of stones on the table. Alice first chooses some CONSECUTIVE piles of stones to play the Nim game with Tom. Also, Alice will make the first move. Alice wants to know how many ways of choosing can make her win the game if both players play optimally.
You are given a sequence a[0],a[1], ... a[N-1] of positive integers to indicate the number of stones in each pile. The sequence a[0]...a[N-1] of length N is generated by the following code:
int g = S;
for (int i=0; i<N; i++) {
a[i] = g;
if( a[i] == 0 ) { a[i] = g = W; }
if( g%2 == 0 ) { g = (g/2); }
else { g = (g/2) ^ W; }
}
Input
There are multiple test cases. The first line of input is an integer T(T ≤ 100) indicates the number of test cases. ThenT test cases follow. Each test case is represented by a line containing 3 integersN, S and W, separated by spaces. (0 < N ≤ 105, 0
Output
For each test case, output the number of ways to win the game.
Sample Input
2
3 1 1
3 2 1
Sample Output
4
5
: n , n NIM , 。
, 。
n , n*(n+1)/2 。
nim[] 1……i i nim[i] 。
nim[i]==nim[j] ,i+1,i+2……j 0, 。
, nim[i]==0, 1……i 。
, 。#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<algorithm>
using namespace std;
int N,S,W;
int a[100010];
int nim[100010];
void init()
{
int g = S;
for (int i=0; i<N; i++)
{
a[i] = g;
if( a[i] == 0 )a[i] = g = W;
if( g%2 == 0 ) g = (g/2);
else g = (g/2) ^ W;
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&N,&S,&W);
init();
nim[0]=a[0];
for(int i=1;i<N;i++)
nim[i]=nim[i-1]^a[i];
long long ans=(long long)N*(N+1)/2;// (long long) WA
sort(nim,nim+N);
int l=1;
for(int i=1;i<N;i++)
{
if(nim[i]==nim[i-1]) l++;
else
{
if(nim[i-1]==0) ans-=l;
ans-=(long long)l*(l-1)/2;//c(l,2)
l=1;
}
}
ans-=(long long)l*(l-1)/2;
printf("%lld
",ans);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
localStorage에 객체를 추가하는 방법은 무엇입니까?이 노트에서는 localStorage에 객체를 삽입하는 방법을 보여드리겠습니다. 경우에 따라 로컬 스토리지 또는 세션 스토리지에 데이터를 개체로 저장해야 할 수 있습니다. 어떻게 이것을 달성할 수 있습니까? 객체가 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.