题解

全部评论 2

• 

  尤里卡突袭者

  

  删除

  正经题解：
  #include <algorithm>
  #include <cstdio>
  using namespace std;
  const long long mod = 998244353;
  const int maxn = 300010;

  int n, m, a;
  long long A[maxn];
  int gcd(int x, int y) {
  while (y) {
  x %= y;
  swap(x, y);
  }
  return x;
  }

  long long SG(long long x) {
  if (a == 0) return x;
  if (x < m + a) return (x / a) & 1;
  x -= 2 * a;
  long long q = x / m, r = x % m;
  if (2 * a <= m) {
  return (r % (2 * a) >= a) ? 1 : ((r >= m - a) << 1);
  }
  return r < m - a ? 0 : min(q + 1, (m - r - 1) / (m - a)) + 1;
  }

  int main() {
  scanf("%d %d %d", &n, &m, &a);
  int g = gcd(a, m);
  m /= g, a /= g;
  long long nim = 0;
  for (int i = 1; i <= n; i++) {
  scanf("%lld", &A[i]);
  A[i] /= g;
  nim ^= SG(A[i]);
  }
  if (nim == 0) {
  printf("0\n");
  return 0;
  }
  if (a == 0) {
  int ans = 0;
  for (int i = 1; i <= n; i++) ans += (nim ^ A[i]) < A[i];
  printf("%d\n", ans);
  return 0;
  }
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
  auto get = [m, a](long long x, long long v) {
  long long l = 0, r = (x - a) / m;
  while (l <= r) {
  long long mid = (l + r) >> 1;
  if (SG((x - a) % m + mid * m) <= v) l = mid + 1;
  else r = mid - 1;
  }
  return l;
  };
  long long v = nim ^ SG(A[i]);
  ans = (ans + get(A[i], v) - get(A[i], v - 1)) % mod;
  }
  printf("%lld\n", ans);
  return 0;
  }

  2025-06-24 来自 上海

  1
• 

  dream

  

  删除

  #include <algorithm>
  #include <cstdio>
  using namespace std;
  const long long mod = 998244353;
  const int maxn = 300010;

  int n, m, a;
  long long A[maxn];
  int gcd(int x, int y) {
  while (y) {
  x %= y;
  swap(x, y);
  }
  return x;
  }

  long long SG(long long x) {
  if (a == 0) return x;
  if (x < m + a) return (x / a) & 1;
  x -= 2 * a;
  long long q = x / m, r = x % m;
  if (2 * a <= m) {
  return (r % (2 * a) >= a) ? 1 : ((r >= m - a) << 1);
  }
  return r < m - a ? 0 : min(q + 1, (m - r - 1) / (m - a)) + 1;
  }

  int main() {
  scanf("%d %d %d", &n, &m, &a);
  int g = gcd(a, m);
  m /= g, a /= g;
  long long nim = 0;
  for (int i = 1; i <= n; i++) {
  scanf("%lld", &A[i]);
  A[i] /= g;
  nim ^= SG(A[i]);
  }
  if (nim == 0) {
  printf("0\n");
  return 0;
  }
  if (a == 0) {
  int ans = 0;
  for (int i = 1; i <= n; i++) ans += (nim ^ A[i]) < A[i];
  printf("%d\n", ans);
  return 0;
  }
  long long ans = 0;
  for (int i = 1; i <= n; i++) {
  auto get = [m, a](long long x, long long v) {
  long long l = 0, r = (x - a) / m;
  while (l <= r) {
  long long mid = (l + r) >> 1;
  if (SG((x - a) % m + mid * m) <= v) l = mid + 1;
  else r = mid - 1;
  }
  return l;
  };
  long long v = nim ^ SG(A[i]);
  ans = (ans + get(A[i], v) - get(A[i], v - 1)) % mod;
  }
  printf("%lld\n", ans);
  return 0;
  }

  1周前 来自 浙江

  0