题解——牛客网Wannafly挑战赛23 B-游戏 （SG函数）

前言

比赛的时候没学过SG函数的蒟蒻以为是道结论题，但是不是QwQ

和dummyummy巨佬一起推了快三个小时的规律

最后去问了真正的巨佬__stdcall

__stdcall面带微笑的告诉我们，这是SG函数的板子题

QwQ

被卡科技了

体验极差

正文

题目

链接：https://www.nowcoder.com/acm/contest/161/B
来源：牛客网

题目描述

小N和小O在玩游戏。他们面前放了n堆石子，第i堆石子一开始有c_i颗石头。他们轮流从某堆石子中取石子，不能不取。最后无法操作的人就输了这个游戏。但他们觉得这样玩太无聊了，更新了一下规则。具体是这样的：对于一堆有恰好m颗石子的石头堆，假如一个人要从这堆石子中取石子，设他要取石子数为d，那么d必须是m的约数。最后还是无法操作者输。
现在小N先手。他想知道他第一步有多少种不同的必胜策略。一个策略指的是，从哪堆石子中，取走多少颗石子。只要取的那一堆不同，或取的数目不同，都算不同的策略。

输入描述:

第一行一个整数n。
接下来一行n个整数，分别代表每堆石子的石子数目。
数据保证输入的所有数字都不超过( 10^{5} )，均大于等于1，且为整数。

输出描述:

一行一个整数代表小$N$第一步必胜策略的数量。

输入

10
47 18 9 36 10 1 13 19 29 1

输出

7

题解

题目让求第一步必胜策略的数量

那就是求第一步走后有多少个状态是必败态

组合的Nim游戏模型

求出SG函数，然后枚举每个数和它的约数

累加一下ans

完毕

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
vector<int> g[100001];
int qz[100001],hz[100002],n,a[100001],SG[100001]={0},f[100001];
int ans=0,maxa; 
void sg(void){
    for(int i=1;i<=n;i++)
        for(int j=1;j<=sqrt(a[i]);j++)
            if(a[i]%j==0){
                if(a[i]/j==j)
                    g[i].push_back(j);
                else{
                    g[i].push_back(j);
                    g[i].push_back(a[i]/j);
                }
            }
    return;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),maxa=max(a[i],maxa);
    SG[0]=0;
    for(int i=1;i<=maxa;i++) {
        int tt;
        for(int k=2,j=4;;j*=4,k+=2) {
            if(i%j==1*(j/4)||i%j==3*(j/4)) tt=k-1;
            if(i%j==2*(j/4)) tt=k;
            if(i%j!=0) break;
        }
        SG[i]=tt;
    }
    sg();
//    for(int i=0;i<=maxa;i++)
//        printf("SG[%d]=%d
",i,SG[i]);
    for(int i=1;i<=n;i++)
        qz[i]=qz[i-1]^SG[a[i]];
    for(int j=n;j>=1;j--)
        hz[j]=hz[j+1]^SG[a[j]];
    for(int i=1;i<=n;i++){
        for(int j=0;j<g[i].size();j++)
            if(!((qz[i-1]^hz[i+1])^SG[a[i]-g[i][j]]))
                ans++;
    }
    printf("%d",ans);
    return 0;
}