ACM训练日记—3月12日

最新推荐文章于 2024-03-16 17:07:58 发布

snayf

最新推荐文章于 2024-03-16 17:07:58 发布

阅读量544

点赞数

本文链接：https://blog.csdn.net/snayf/article/details/79533503

版权

周末跟风刷版题刷嗨了，居然忘记写日记，今天补上吧。

这次就整理下之前牛客网比赛的题目和Nim博弈和SG函数。

Wannafly挑战赛11

1，白兔的分身术
白兔学会了分身术。
一开始有一只白兔，接下来会进行k轮操作，每一轮中每一只白兔都会变成p只白兔。要求k轮后白兔的总数恰好为n。要求找到两个正整数p,k，最大化p+k

水题，其实就是输出n+1，千万别把n因子分解了，否则就掉坑里了。

2，白兔的式子
已知f[1][1]=1,f[i][j]=a*f[i-1][j]+b*f[i-1][j-1](i>=2,1<=j<=i)。对于其他情况f[i][j]=0有T组询问，每次给出a,b,n,m，求f[n][m] mod (998244353)。

这道题其实看到公式就能自然的反映出这是杨辉三角，然后把这个三角写一下就能发现规律了，就是如果求(n,m)的值，那么就是C(n-1,m-1)*a^(n-m)*b^(m-1)%mod。注意要用Lucas定理优化，还要用快速幂。

代码：

using namespace std;
ll mod=998244353;
long long F[100010];
ll exp_mod(ll a, ll b, ll p)
{
ll res = 1;
while(b)
{
if(b&1) res = (res * a) % p;
a = (a*a) % p;
b >>= 1;
}
return res;
}
void init(long long p)
{
F[0] = 1;
for(int i = 1;i <= p;i++)
F[i] = F[i-1]*i%mod;
}
long long inv(long long a,long long m)
{
if(a == 1) return 1;
return inv(m%a,m)*(m-m/a)%m;
}
long long Lucas(long long n,long long m,long long p)
{
long long ans = 1;
while(n&&m)
{
long long a = n%p;
long long b = m%p;
if(a < b) return 0;
ans = ans*F[a]%p*inv(F[b]*F[a-b]%p,p)%p;
n /= p;
m /= p;
}
return ans;
}
int main()
{
ll n,m,a,b;
int T;
ll ans;
init(100005);//一定要预处理这个
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld%lld%lld",&a,&b,&n,&m);
if(m>n)
{
cout<<0<<endl;
continue;
}
ans=Lucas(n-1,m-1,mod)%mod;
ans=(ans*exp_mod(a,n-m,mod))%mod;
ans=(ans*exp_mod(b,m-1,mod))%mod;
cout<<ans<<endl;
}
}

Nim博弈

尼姆博弈模型，大致上是这样的：
有3堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取1个，多者不限，最后取光者得胜。

以下参考：http://blog.csdn.net/u013514928/article/details/69055286

1、首先自己想一下，就会发现只要最后剩两堆物品一样多(不为零)，第三堆为零，那面对这种局势的一方就必败。
那我们用(a,b,c)表示某种局势，首先(0,0,0)显然是必败态，无论谁面对(0,0,0) ，都必然失败；第二种必败态是(0,n,n)，自己在某一堆拿走k（k ≤ n）个物品，不论k为多少，对方只要在另一堆拿走k个物品，最后自己都将面临(0,0,0)的局势，必败。仔细分析一下，(1,2,3)也是必败态，无论自己如何拿，接下来对手都可以把局势变为(0,n,n)的情形。

那这种奇异局势有什么特点呢？
也不知谁这么牛逼，竟然能把这种局势和二进制联系在一起
这里说一种运算符号，异或'^',a^b=a'b+ab'（a'为非a）

我们用符号XOR表示这种运算，这种运算和一般加法不同的一点是1 XOR 1 = 0。先看(1,2,3)的按位模2加的结果：
1 = 二进制01
2 = 二进制10
3 = 二进制11 XOR
———————
0 = 二进制00 (注意不进位)

对于奇异局势(0,n,n)也一样，结果也是0
任何奇异局势(a,b,c)都有a XOR b XOR c = 0

如果我们面对的是一个非必败态(a,b,c)，要如何变为必败态呢？
假设 a < b < c，我们只要将 c 变为a XOR b，即可。因为有如下的运算结果：
a XOR b XOR (a XOR b)=(a XOR a) XOR (b XOR b) = 0 XOR 0 = 0
要将c 变为a XOR b，只要对 c进行 c-(a XOR b)这样的运算即可。

2、尼姆博弈模型可以推广到：有n堆若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。
这个游戏中的变量是堆数k和各堆的物品数N1，N2，……，Nk。
对应的组合问题是，确定先手获胜还是后手获胜以及两个游戏人应该如何取物品才能保证自己获胜。

3、为了进一步理解Nim取物品游戏，我们看看特殊情况。
如果游戏开始时只有一堆物品，先手则通过取走所有的物品而获胜。现在设有2堆物品，且物品数量分别为N1和N2。游戏者取得胜利并不在于N1和N2的值具体是多少，而是取决于它们是否相等。也就说两堆的策略我们有了，现在我们如何从两堆的取子策略扩展到任意堆数中呢？

首先回忆一下，每个正整数都有对应的一个二进制数，例如：57(10) = 111001(2) ，即：57(10)=2^5+2^4+2^3+2^0。于是，我们可以认为每一堆物品数由2的幂数的子堆组成。这样，含有57枚物品大堆就能看成是分别由数量为25、24、23、20的各个子堆组成。

现在考虑各大堆大小分别为N1，N2，……Nk的一般的Nim博弈。将每一个数Ni表示为其二进制数（数的位数相等，不等时在前面补0）：
N1 = as…a1a0
N2 = bs…b1b0
……
Nk = ms…m1m0
如果每一种大小的子堆的个数都是偶数，我们就称Nim博弈是平衡的，而对应位相加是偶数的称为平衡位，否则称为非平衡位。因此，Nim博弈是平衡的，当且仅当：
as +bs + … + ms 是偶数，即as XOR bs XOR … XOR ms = 0
……
a1 +b1 + … + m1 是偶数，即a1 XOR b1 XOR … XOR m1 = 0
a0 +b0 + … + m0是偶数，即a0 XOR b0 XOR … XOR m0 = 0

于是，我们就能得出尼姆博弈中先手获胜策略：
Bouton定理：先手能够在非平衡尼姆博弈中取胜，而后手能够在平衡的尼姆博弈中取胜。即状态(x1, x2, x3, …, xn)为P状态当且仅当x1 xor x2 xor x3 xor … xor xn =0。这样的操作也称为Nim和(Nim Sum)。

SG函数

来自：http://blog.csdn.net/wu_tongtong/article/details/79118066

首先定义mex运算
这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数
例如mex{0,1,2,4}=3，mex{2,3,5}=0，mex{}=0

对于任意状态xx，定义 SG(x)=mex(S)SG(x)=mex(S)，其中SS是xx后继状态的SG函数值的集合
如xx有三个后继状态分别为SG(a),SG(b),SG(c)SG(a),SG(b),SG(c)，那么SG(x)=mex(SG(a),SG(b),SG(c))SG(x)=mex(SG(a),SG(b),SG(c))
SGSG函数的终态为SG(x)=0SG(x)=0，当且仅当xx为必败点时

取石子问题
有1堆n个的石子，每次只能取{ 1, 3, 4 }个石子，先取完石子者胜利，那么各个数的SG值为多少？
SG[0]=0，f[]={1,3,4},
x=1 时，可以取走1 - f{1}个石子，剩余{0}个，所以 SG[1] = mex{SG[0]}= mex{0} = 1
x=2 时，可以取走2 - f{1}个石子，剩余{1}个，所以 SG[2] = mex{SG[1]}= mex{1} = 0
x=3 时，可以取走3 - f{1,3}个石子，剩余{2,0}个，所以 SG[3] = mex{SG[2],SG[0]} = mex{0,0} =1
x=4 时，可以取走4- f{1,3,4}个石子，剩余{3,1,0}个，所以 SG[4] = mex{SG[3],SG[1],SG[0]} = mex{1,1,0} = 2
x=5 时，可以取走5 - f{1,3,4}个石子，剩余{4,2,1}个，所以SG[5] = mex{SG[4],SG[2],SG[1]} =mex{2,0,1} = 3
以此类推…..