2022牛客多校（二）

2022牛客多校（二）

一、比赛小结

比赛链接："蔚来杯"2022牛客暑期多校训练营2

二、题目分析及解法（基础题） C、Link with Nim Game

题目链接：C-Link with Nim Game

题意：

有 n 堆石头，第 i 堆石头有 ai 个。Alice 和 Bob 轮流进行操作，Alice 先。每次操作可以从某一堆石头中取出正整数个石头，无法完成操作者输。在双方都采取最优策略的情况下，必败的一方希望尽可能慢的结束游戏，必胜的一方希望尽可能快的结束游戏。

求“游戏结束时进行的操作数量”和“第一轮可能进行的操作种类数”

题解：

两个问题都不是特别好处理，我们先用 nim 推些结论。若当前局面的石头数异或和为 0 ，则为必败局面，若当前局面的石头数异或和不为 0 ，则为必胜局面。仔细分析的话，他们的选取石头还是限制性挺高的，必胜者一方面需要让当前局面变成异或和为 0 的情况，一方面想快速将石子拿完。必败者则一方面需要让当前局面变成异或和不是 0 ，一方面想慢点拿完石头。

事实上，对于必败者，他可以通过选取一堆并拿走一颗石头，进而让必胜者也只能那走一块石头，可以考虑 lowbit 来思考。这样来看，问题就明了了。

若初始局面为必败态，则 ans1 为所有石头的和， ans2 约为石头堆数（需要用 lowbit 的限制筛掉一些）。若初始局面为必胜态，则 ans1 为所有石头和 - 先手第一次拿走的，ans2 可由相应情况来计数。

代码：

对于集合 s 的元素 e 和对应的a[i] 有：a[i] -= 1 等价于 a[i] ^= e

#include 
#define int long long
using namespace std;
const int maxn = 1e5 + 5;
int n;
int a[maxn];
int sum, xsum;
// lose
void lose() {
  set s, t;
  for (int i = 1; i {n-2k}\choose{k}} 
       
      
    = 1;
      k >>= 1;
      if ((quickpow(x, i) * quickpow(b, k) + 1) % mod == 0) k += (mod - 1 >> 1);
    } while (i % 2 == 0);
    ans = quickpow(x, i + 1 >> 1) * quickpow(b, k >> 1) % mod;
  }
  if (ans * 2 > mod) ans = mod - ans;
  return ans;
}
// 蝴蝶变换
void change(ll* a, int len) {
  static int rev[maxn];
  rev[0] = 0;
  for (int i = 0; i > 1] >> 1);
    if (i & 1) rev[i] |= len >> 1;
  }
  for (int i = 0; i  INTT , O(nlogn)
void NTT(ll* a, int len, int flag) {
  change(a, len);
  for (int h = 2; h