发布于

lp2197 NIM游戏

图文无关，因为空和白玩的游戏中没有一个是ICG类的。

NIM游戏是一类经典的博弈论题目。
众所周知，NIM游戏的结果就是把所有的答案异或起来即可。为什么可以这么做呢？
我们定义，对于一个「均衡组合博弈（ICG）」 ，我们定义两种局面状态：P（先手必败）和N（先手必胜）。
首先我们可以知道，在ICG中，博弈是一定会终止的；同时，终止局面是P局面。如果说一个局面的所有子局面都是N局面或者P局面，那么这个局面也一定是N局面或者P局面：这是因为N局面和P局面存在性质：
一个局面是P局面，当且仅当它的所有子局面都是N局面；一个局面是N局面，当且仅当它的所有子局面中存在一个是P局面。
这也就意味着，对于任何一种状态，我们都可以判定它是N状态还是P状态。
那么，初始状态的N-P性是可以判断的。
如何计算一个局面的N-P性呢？
我们定义一种运算，使得：
P局面经过这种运算只能变成N局面；
N局面经过这种运算可以变成P局面。
当我们用一个数列描述一个局面后，我们惊讶地发现：异或——这里指的是将局面中的每一个子部分异或起来——是满足这个性质的。
我们定义，异或值为零的局面是必败局面；异或值非0的局面是必胜局面。
我们将描述这个局面的数列异或起来，如果它等于零，那么任意一种「减少」操作——导致它的一个值减少的，一定会导向一种P局面；
而对于一种P局面，依据按位异或的特性，一定可以通过减少最大的数，来变更想变更的任意一位。
故而，我们发现，对于任意一种局面，我们可以用异或运算来判断它的N-P性。
事实上，两者之间并不存在那么直接的数学上的对应关系。可以将NIM游戏理解为一个数学模型。
这是一种指代关系。换句话说，为了更方便地处理它，
我们可以将这个局面转化为数学模型，而异或运算刚好满足其性质——这并不是说异或运算本身就是这个局面的变化。
当理解这一点之后，异或的意义就很显然了。

#include<iostream>
#include<cstdio>
using namespace std;
int n,a[10005];
void init(){
    scanf("%d",&n);
    int x=0;
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        x^=a[i];
    }
    if(x){
        puts("Yes");
    }else{
        puts("No");
    }
    return;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}

 

发布于

Lucas定理

首先给出关于Lucas定理的简要证明：
定义：
$$ a=a_{k}*p^{k}+a_{k-1}*p^{k-1}+…+a_{1}*p+a_{0}=\sum_{i=1}^{k}a_{i}^p{i} $$
$$ b=b_{k}*p^{k}+b_{k-1}*b^{k-1}+…+b_{1}*p+b_{0}=\sum_{i=1}^{k}b_{i}^p{i} $$
求证：
$$ C_{a}^{b}=C_{a_{k}}^{b_{k}}*C_{a_{k-1}}^{b_{k-1}}…C_{a_{0}}^{b_{0}} $$

首先我们证明引理一：
$$ (1+x)^p≡1+x^p\ (mod\ p) $$
根据组合数基本性质，我们有：
$$\forall j\in [1,p-1],C_{p}^{j}=\frac{p}{j}*C_{p-1}^{j-1}≡0(mod\ p) $$

$$∴(1+x)^p≡\sum_{i=1}^{p}C_{p}^{i}*x^i≡1+x^p(mod\ p) $$
于是我们得到结论：
$$(1+x)^a≡\prod_{i=1}^{k}(1+x)^{p^k*a_{k}}≡\prod_{i=1}^{k}(1+x^{p^{k}})^{a_{k}}(mod\ p)\ (1)$$
根据进制的基本性质和幂的基本性质，我们有：
$$b=\sum_{i=1}^{k}b_{i}^p{i},x^b=\prod_{i=1}^{k}x^{p^k*b_{i}}$$
并且我们知道，用上述方法表示\(p\)进制数，是完全等价的。即，两者的集合构成双射。

故而我们比较\((1)\)式展开后左右各项，可以得到：
$$\forall b\in [1,a],C_{a}^{b}≡\prod_{i=1}^{k}C_{a_{i}}^{b_{i}}(mod\ p)$$

证毕。

故而对于实际处理问题，只需要逆向秦九韶即可。

 

#include<iostream>
#include<cstdio>
using namespace std;
long long n,m,p,inv[100005],fac[100005];
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))

//y取x 
inline long long C0(long long x,long long y){
    return ((x>y)?0:(x?fac[y]*inv[x]*inv[y-x]%p:1))%p;
}
//模p意义下的y取x 
inline long long C(long long x,long long y){
    return ((x>y)?0:((y>=p)?C(x/p,y/p)*C0(x%p,y%p):C0(x%p,y%p)))%p;
}
void init(){
    scanf("%lld%lld%lld",&n,&m,&p);
    fac[0]=fac[1]=inv[0]=inv[1]=1;
    for(int i=2;i<=p;++i){
        fac[i]=fac[i-1]*i%p;
        inv[i]=(p-p/i)*inv[p%i]%p;
    }
    for(int i=2;i<=p;++i){
        inv[i]*=inv[i-1];
        inv[i]%=p;
    }
    printf("%lld\n",C(n,n+m)%p);
} 
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        init();
    }
    return 0;
}