1048 游戏 sg函数变式 博弈论

本文主要是介绍1048 游戏 sg函数变式 博弈论，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

链接：https://ac.nowcoder.com/acm/contest/26656/1048
来源：牛客网

题目描述

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

输入描述:

第一行一个整数n。
接下来一行n个整数，分别代表每堆石子的石子数目。
数据保证输入的所有数字都不超过10

⁵

，均大于等于1，且为整数。

输出描述:

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

示例1

输入

复制 10 47 18 9 36 10 1 13 19 29 1

10
47 18 9 36 10 1 13 19 29 1

输出

复制 7

7

 

分析

标准的集合类nim游戏问题。

普通的集合类nim游戏：有几种取法，在n堆石子里取，问最终结果。将每一堆石子的sg值算出来就是答案。

这题：每堆石子可以取自己的因子的数量的石子，从n堆取，问最终结果。要将每一堆石子的sg值算出来就很复杂，需要用到之前的状态，而且还要求出有多少种不同取法。

问题1：算出每堆石子的sg值

 

由于石子数目小于一万，所以可以从小到大dp，预处理出所有石子的sg值，当求后面的石子的sg值的时候，前面所有石子的sg值已经求过了

设f[i] 表示 i 个石子的sg值

状态转移：设i 的因子d，f[i] = mex(f[i-d1],f[i-d2],f[i-d3]....)

 

问题2：通过算出的sg值，判断第一步有多少取法

 

假设已经求出了所有sg值的异或和 sum

要获得胜利，就要让对方变成必败状态，即sg值为0的状态。

让sum 异或 每堆石子数目。消去当前堆石子的总数的影响。

遍历当前堆石子的所有因子，如果异或这个因子能够使sum 值为0，即为必败状态。方案数 + 1

 

#include<bits/stdc++.h>
#define TLE ios::sync_with_stdio(0),cin.tie(0)
#define endl "\n"
#define FILE "a"
#define pb push_back
#define gg exit(0);
#define rt return;
#define bd cout<<"debug"<<endl;
#define db(x) cout<<#x<<':'<<x<<endl;
#define dbb(i,a) cout<<#i<<':'<<i<<' '<<#a<<':'<<a<<' '<<endl;
#define dbbb(i,a,b) cout<<#i<<':'<<i<<' '<<#a<<':'<<a<<' '<<#b<<':'<<b<<endl;
#define YES cout<<"YES"<<endl;
#define TIME cout<<"RuningTime: "<<clock()<<"ms\n";
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define None cout<<-1<<endl;
#define el cout<<endl;
#define x first
#define y second
#define V vector
#define fo(i,j,n) for(int i = j;i<=n;i++)
#define of(i,n,j) for(int i = n;i>=j;i--)
#define all(a) a.begin(),a.end()
#define alll(a) a.begin()+1,a.end()
#define ms(a,b) memset(a, b, sizeof(a))
#define lowbit(x) (x&-x)
#define gcd(a,b) __gcd(a,b)
#define DEBUG 11243
using namespace std;
void clapping() {
    #if DEBUG == 1
    srand(time(NULL)+rand());
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    #endif
}
template<class T>inline void read(T &res) {
    char c;T flag = 1;
    while((c = getchar()) < '0' || c > '9') if(c == '-') flag = -1;res = c - '0';
    while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
typedef pair<int,int> pii;
typedef pair<long,long>pll;
typedef long long ll;
const int inf = 1e9;
const ll INF = 1ll<<60;
const double eps = 1e-8;
int dy[] = {1,0,-1,0,1,1,-1,-1};
int dx[] = {0,1,0,-1,1,-1,1,-1};
template<class T> T qmi(T a,T b,T p) {
    T res = 1;
    for(;b;b>>=1,a=1ll*a*a%p)
        if(b&1)res = 1ll*res*a%p;
    return res;
}
template<class T> T exgcd(T a,T b,T &x,T &y) {
    if(b == 0) {x = 1;y = 0;return a;}
    ll d = gcd_ed(b,a%b,y,x);
    y = y - a / b * x;
    return d;
}
/*文档区


*/

//-------------------------代码----------------------------

//#define int ll
const int mod = 1e9 +7,md = 1e9+6,N = 1e5+10;
int a[N];
int sg[N];
vector<int>G[N];
int vis[N];

void solve()
{
    int cnt = 0;
    for(int i = 1;i<N;i++) {
        cnt ++ ;
        int k = sqrt(i);
        for(int j = 1;j<=k;j++) {
            if(i % j == 0) {
                vis[sg[i-j]]=cnt;
                if(j*j!=i) vis[sg[i-i/j]]=cnt;
            }
        }
        for(int j = 0;j<=N-10;j++)
            if(vis[j] != cnt) 
            {
                sg[i] = j;
                break;
            }
    }
    int n;cin>>n;
    int sum = 0;
    for(int i = 1;i<=n;i++) {
        cin>>a[i],sum ^= sg[a[i]];
    }
    int ans = 0;
    for(int i = 1;i<=n;i++) {
        sum ^= sg[a[i]];
        int k = sqrt(a[i]);
        for(int j = 1;j<=k;j++) {
            if(a[i] % j == 0) {
                if((sg[a[i] - j]^sum) == 0) {ans ++ ;}
                if(j * j != a[i] && ( sg[a[i] - a[i] / j] ^ sum) == 0) ans ++ ;
            }
        }
        sum ^= sg[a[i]];
    }
    cout<<ans<<endl;
}

signed main(){
    clapping();TLE;

//    int t;cin>>t;while(t -- )
    solve();
//    {solve(); }
    return 0;
}

/*样例区


*/

//------------------------------------------------------------

 

这篇关于1048 游戏 sg函数变式 博弈论的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！