題目鏈接：點擊查看

題目大意：給出n個數(shù)，兩個人輪流按照規(guī)則操作，不能操作的人即為失敗，規(guī)則很簡單，每次找一個質(zhì)數(shù)p的k次冪，記做x=，將數(shù)組中所有包含x倍數(shù)的數(shù)都除以x，必須保證至少有一個數(shù)可以除以x，如此往復(fù)

題目分析：因為涉及到了質(zhì)數(shù)，第一反應(yīng)是唯一分解定理，這個題難就難在該如何轉(zhuǎn)換模型，其實熟悉尼姆博弈的大佬們一眼就能將這個題目轉(zhuǎn)換為多個子游戲之和，回到這個題目，我們可以將這個題目轉(zhuǎn)換為以每個質(zhì)數(shù)為子游戲的博弈，最后異或一下每個質(zhì)數(shù)所代表的sg函數(shù)，再判斷一下結(jié)果就行了

具體的話，因為每個子游戲都不能互相影響答案，所以選擇n個數(shù)中的每一個數(shù)作為子游戲肯定是不合適的。因為每一次操作都會對其他不同的數(shù)字進(jìn)行操作，那我們可以考慮一下關(guān)于每個質(zhì)數(shù)的冪次，比如當(dāng)前質(zhì)數(shù)p的冪次：1,2,3....k，和另一個質(zhì)數(shù)pp的冪次：1,2,3....k，是互不影響的，所以我們可以將每個質(zhì)數(shù)當(dāng)做一個子游戲

有了子游戲，我們就該設(shè)置sg函數(shù)了，因為sg函數(shù)是基于當(dāng)前狀態(tài)和后續(xù)狀態(tài)才能轉(zhuǎn)移的，所以我們需要考慮每個狀態(tài)的后續(xù)狀態(tài)該如何轉(zhuǎn)移，其實很好實現(xiàn)，比如還是假設(shè)，當(dāng)前質(zhì)數(shù)p在n個數(shù)中總共出現(xiàn)過的冪次有1,1,2,3,5，那么顯然，兩個1的貢獻(xiàn)我們可以合并成一個1的貢獻(xiàn)，因為當(dāng)我們對于n個數(shù)同時除以p的1次冪時，兩個1都會受到相同的影響，從這里我們可以得到多個相同的冪次都可以壓縮為一個冪次的貢獻(xiàn)，再然后我們可以枚舉每一個位上的貢獻(xiàn)，就可以得到后續(xù)狀態(tài)了，比如我們假設(shè)當(dāng)前枚舉到了k=3，我們該如何計算貢獻(xiàn)的冪次為3下的后續(xù)狀態(tài)呢：

對于當(dāng)前冪次小于k的位置，不做改變

對于當(dāng)前冪次大于等于k的位置，讓其減去k(即除以該冪次的數(shù))

這樣對于冪次為3的貢獻(xiàn)就將1,1,2,3,5變?yōu)榱?,1,2,0,2

另外對于sg遞歸寫法最終要的就是邊界問題了，顯然，當(dāng)狀態(tài)全部變?yōu)?時，該狀態(tài)的sg值一定是0，返回0即可

還有需要強調(diào)的一個細(xì)節(jié)就是，因為每個狀態(tài)的sg值都是固定的，雖然前置狀態(tài)不確定，但后續(xù)狀態(tài)一定是確定了的，所以我們可以記憶化搜索這個題目，防止遍歷重復(fù)分支

可以用zx學(xué)長的簡單寫法，map套set來模擬上述過程，網(wǎng)上更普遍的是一種用二進(jìn)制狀壓的寫法，因為最小的質(zhì)數(shù)時2，而每個數(shù)最大只有1e9，即使是每次都除以2，最多也只需要除32次，所以用一個int類型的變量狀壓即可，第一位代表著1，第二位代表著和2，以此類推，我是用的狀態(tài)壓縮

還有一個小細(xì)節(jié)。。我也不知道為什么素數(shù)表打了個1e4會WA，后來改成1e5就A了，（其實正宗的唯一分解定理是不需要素數(shù)表的，直接從1枚舉到sqrt(n)，時間復(fù)雜度也為O(sqrt(n)），但我為了省時間，預(yù)處理打了個素數(shù)表

對了，關(guān)于二進(jìn)制情況下該怎么得到后續(xù)狀態(tài)，這個有點難理解，不過原理和上述的一模一樣，先掛位運算的公式：

(x>>i)|(x&(1<<i-1)-1)? ? （i為枚舉到了哪一位冪次，x為當(dāng)前狀態(tài)）

稍微解釋一下這個公式吧，前面的(x>>i)是將大于等于k的數(shù)減去了k，后面(1<<i-1)-1是為了先讓小于k的那些位置上都變?yōu)?，然后再與原狀態(tài)取與運算，就能得到原位置上小于k的數(shù)有哪些了，最后讓原本小于k的數(shù)，和大于等于k的數(shù)減去了k之后的二進(jìn)制，取一下或運算，就是新的狀態(tài)了

不得不佩服二進(jìn)制和位運算的精妙之處，若是仍然不理解的話，完全可以用map套set來寫，那個更好理解更好實現(xiàn)，就是在得到后續(xù)狀態(tài)的時候需要自己手動模擬上述證明的過程，區(qū)別不算很大

直接掛代碼吧：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int pri[N];bool vis[N];int cnt;unordered_map<int,int>sg,mp;void P()//歐拉線性篩 {for(int i=2;i<N;i++){if(!vis[i])pri[cnt++]=i;for(int j=0;j<cnt&&pri[j]*i<N;j++){vis[pri[j]*i]=true;if(i%pri[j]==0)break;}} }void solve(int num)//唯一分解定理 {for(int i=0;i<cnt&&pri[i]*pri[i]<=num;i++){int sum=0;while(num%pri[i]==0){sum++;num/=pri[i];}if(sum)mp[pri[i]]|=1<<(sum-1);if(num==1)break;}if(num>1)mp[num]|=1; }int getpos(int x)//得到最高位的位置 {int ans=0;while(x){x>>=1;ans++;}return ans; }int get_sg(int x)//記憶化搜索計算sg函數(shù) {if(sg[x])return sg[x];if(x==0)return 0;map<int,bool>mex;int pos=getpos(x);for(int i=1;i<=pos;i++)mex[get_sg((x>>i)|(x&(1<<i-1)-1))]=true;for(int i=0;;i++)if(!mex[i])return sg[x]=i; }int main() { // freopen("input.txt","r",stdin);P();int n;scanf("%d",&n);for(int i=1;i<=n;i++){int num;scanf("%d",&num);solve(num);}int ans=0;for(auto it=mp.begin();it!=mp.end();it++)ans^=get_sg(it->second);if(ans)printf("Mojtaba\n");elseprintf("Arpa\n");return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 850C Arpa and a game with Mojtaba(博弈+sg函数)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。