高級博弈論，POJ 2975 Nim（博弈論）

?

【題目鏈接】?http://poj.org/problem?id=2975

?

【題目大意】

　　問在傳統的nim游戲中先手必勝策略的數量

?

【題解】

　　設sg=a1^a1^a3^a4^………^an，當sg為0時為必敗態，
　　因此先手只需改變一個aj，讓其減少m，使得sg^aj^(aj-m)=0即可讓對手處于必敗態，
　　即先手必勝策略，因為異或為0的兩個數相同，所以sg^aj=aj-m，
　　即m=aj-sg^aj，因為m大于0，所以aj>sg^aj，至此我們就得到了必勝策略的重要條件

?

【代碼】

#include <cstdio>
#include <algorithm>
using namespace std;
int a[1010],n;
int main(){while(~scanf("%d",&n),n){int sg=0,ans=0;for(int i=0;i<n;i++)scanf("%d",&a[i]),sg^=a[i];for(int i=0;i<n;i++)if((sg^a[i])<a[i])ans++;printf("%d\n",ans);}return 0;
}