SRM 20

时间:2024-04-20 10:06:33

  本来T1想出给一堆数求异或最大值的,然后觉得太模板不好……就改成了现在这样(好像跟T2难度差不多了?不管辣

魔法弹

  先把最大线性无关组求出来,就不会有重复的问题了。接下来单独考虑每个位,如果某个上所有数都是0,这个位贡献为0,否则贡献为$w*2^{r-1}$,w是位权,r是矩阵的秩,二项式定理可证。

不净的圣杯

  对于每个a(1<=a<=m)求出n个数中有多少个是它的倍数,设为b,那么gcd为a的倍数的方案数就是$2^b-1$,然后容斥即可。(感觉比T1简单)

  上面这行看不懂的话,那(我能怎么办)看看标程应该就行了。

灵魂觉醒

  原题:PE595

  我们需要先对于每个n,m(m<=n)求出1到n的所有排列中,粘合之后剩下m张卡片的排列数量,设为f(n,m),拿这个递推一下期望方程就可以了。

  然后就是怎么求f(n,m)的问题了,显然当m<n时,f(n,m)=f(m,m)*C(n-1,m-1),至于f(n,n)可以直接用n!减去前面的f(n,m)。然后这题就没了。

SRM 20