补题：E

题意

假设存在长度为\(n\)的自然数序列，我们在其上进行一个双人游戏。每一轮，当前玩家需要进行如下操作（假设\(X\)为这个状态下序列最大值）：

  • 若\(X=0\)，当前玩家直接胜利。
  • 否则，选择一个\([1,X]\)中的整数\(m\)。
  • 然后，将序列中所有\(b_i\)​都模以\(m\)​。

现在有长为\(n\)的序列\(\{a_i\}\)​，我们可以选择任意满足每一项为不超过\(a_i\)的正整数的序列作为游戏初始状态，请问有多少种初始状态能使得先手必胜？答案对\(998244353\)取模后输出。

解析

注意到，序列中的\(0\)是一只不会变的，而且重复出现的数字都会一致变化。因此我们可以将游戏中的状态表述为正整数集的子集。

首先\(\{1\}\)和\(\{2\}\)肯定是先手必败态了，\(\{1,2\}\)则是先手必胜的。下面考虑\(\max(S)\ge 3\)的集合\(S\)。

容易注意到，若\(S\)​中有奇数，那么先手直接模以\(2\)​就能取胜，因此先手必败态都要是偶数。另一方面，若都是偶数的\(S\)​中存在模\(4\)​余\(2\)​的元素，那么先手模\(4\)​​后，后手就会进入必败态，故先手必败态必须要都是\(4\)​的倍数。接下来，我们来考虑对于都是\(4\)​的倍数的集合，先手模\(3\)是否会是必胜的。

注意到，这样只会有两种情况先手不一定必胜：

  • \(S\)中同时存在模\(3\)余\(1\)和余\(2\)的元素。
  • \(S\)中元素都是\(3\)的倍数。

对于第一种情况，手玩一下可以发现真正先手必败的状态只是\(\{4,8\}\)，其余情况都会存在大于\(12\)的若干\(4\)​的倍数，先手模\(12\)就能将后手置于必败态；对于第二种情况，我们没有好的判定方法。

但是，不超过\(\max\{a_i\}\)的\(12\)的倍数至多有\(\lfloor\frac{200}{12}\rfloor=16\)种，这样我们可以对\(S\)​做一个状压 DP 来判断是否是必败态。此外还有一点就是这个集合\(S\)并不对应于原来的初始状态，这个也用状压 DP 计数一下就好了（大概也可以容斥，不过这里不影响复杂度了）。

代码

#include <bits/stdc++.h>
typedef long long ll;
const ll ha = 998244353;
const int maxn = 401;
int mod_v[maxn][maxn];
void calc_mod_v() {
  for(int i = 1; i < maxn; i ++) {
    for(int j = 1; j < maxn; j ++) {
      mod_v[i][j] = i % j;
    }
  }
}

const int maxb = 17;
int f[1 << maxb];
void calc_dp_state(int s) {
  int &th = f[s];
  
  int high = 0;
  for(int i = 0; i < maxb; i ++) {
    if((1 << i) & s) {
      high = i + 1;
    }
  }
  high *= 12;
  
  th = 0;
  for(int i = 5; i <= high; i ++) {
    int new_s = 0, cur = 0;
    bool al_1 = true, al_2 = true;
    bool has_4 = false, has_8 = false, o_48 = false;
    for(int j = 0; j < maxb; j ++) {
      if((1 << j) & s) {
        const int tv = (j + 1) * 12;
        const int nv = mod_v[tv][i];
        if(nv) {
          al_1 &= (nv == 1);
          al_2 &= (nv == 2);
          has_4 |= (nv == 4);
          has_8 |= (nv == 8);
          o_48 |= (nv != 4 && nv != 8);
          if(!mod_v[nv][12]) {
            new_s |= (1 << (nv / 12 - 1));
          } else {
            cur ++;
          }
        }
      }
    }
    if(new_s > 0 && cur == 0) {
      if(!f[new_s]) {
        th = 1; break;
      }
    }
    if(cur > 0 && new_s == 0) {
      if(al_1 || al_2 || (has_4 && has_8 && !o_48)) {
        th = 1; break;
      }
    }
  }
}

ll f_48[maxn][4];
ll g[2][1 << maxb];

int n, A[maxn];
int main() {
  calc_mod_v();
  scanf("%d", &n);
  ll ret = 1;
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &A[i]);
    ret = ret * A[i] % ha;
  }
  std::sort(A + 1, A + 1 + n);
  ret --;
  if(A[1] >= 2) ret --;
  ret = (ret + ha) % ha;
  
  f_48[0][0] = 1;
  for(int i = 1; i <= n; i ++) {
    for(int j = 0; j < 4; j ++) {
      ll &th = f_48[i][j]; th = 0;
      for(int k = 0; k < 2; k ++) {
        if((1 << k) & j) {
          const int v = (k + 1) * 4;
          if(v > A[i]) break;
          th = (th + f_48[i - 1][j] + f_48[i - 1][j ^ (1 << k)]) % ha;
        }
      }
    }
  }
  ret = (ret + ha - f_48[n][3]) % ha;

  memset(f, 0xff, sizeof(f));
  f[0] = 1; g[0][0] = 1;
  for(int i = 1; i <= n; i ++) {
    ll *now = g[i & 1];
    const ll *pre = g[(i & 1) ^ 1];
    int bound = A[i] / 12;
    memset(now, 0, sizeof(g[0]));
    for(int s = 0; s < (1 << bound); s ++) {
      for(int j = 0; j < bound; j ++) {
        if((1 << j) & s) {
          now[s] = (now[s] + pre[s] + pre[s ^ (1 << j)]) % ha;
        }
      }
    }
  }
  for(int s = 1; s < (1 << maxb); s ++) calc_dp_state(s);
  for(int s = 1; s < (1 << maxb); s ++) {
    ret = (ret - g[n & 1][s] * (1 - f[s]) + ha) % ha;
  }
  printf("%lld\n", ret);
  return 0;
}