2025-05-25 17:45:23
发布于：上海
28阅读
0回复
0点赞
#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 998244353;
// 函数用于计算给定Ai下满足条件的x的数量
long long countValidMoves(long long Ai, long long m, long long a) {
if (a == 0) {
// 当a=0时，x必须是m的正整数倍，即x=km(k≥1)
// 最大的k满足km ≤ Ai，即k ≤ floor(Ai/m)，但k必须≥1
// 因此，k的最大值为floor((Ai-1)/m)
if (Ai < m) return 0; // 没有合法的x
long long K = (Ai - 1) / m;
return K;
} else {
// 当a≠0时，x必须满足x≡a mod m，即x=km+a(k≥0)
// 最大的k满足km + a ≤ Ai，即k ≤ floor((Ai-a)/m)
// 因此，k的最大值为floor((Ai-a)/m)
if (Ai < a) return 0; // 没有合法的x
long long K = (Ai - a) / m;
return K + 1; // k从0到K，共K+1个值
}
}
int main() {
long long N, m, a;
cin >> N >> m >> a;
vector<long long> A(N);
for (int i = 0; i < N; i++) {
cin >> A[i];
}
// 计算每个Ai的SG值的异或和（不考虑第一次操作）
long long xorSum = 0;
for (int i = 0; i < N; i++) {
long long Ai = A[i];
long long sg;
if (a == 0) {
sg = (Ai / m) % 2;
} else {
sg = ((Ai - a) / m) % 2;
}
xorSum ^= sg;
}
long long total = 0;
for (int i = 0; i < N; i++) {
long long Ai = A[i];
long long currentSG;
if (a == 0) {
currentSG = (Ai / m) % 2;
} else {
currentSG = ((Ai - a) / m) % 2;
}
// 计算移除x后的新SG值
long long count = 0;
if (a == 0) {
// x = k*m (k≥1)
long long maxK = (Ai - 1) / m;
for (long long k = 1; k <= maxK; k++) {
long long newAi = Ai - k * m;
long long newSG;
if (a == 0) {
newSG = (newAi / m) % 2;
} else {
newSG = ((newAi - a) / m) % 2;
}
if ((xorSum ^ currentSG ^ newSG) == 0) {
count++;
}
}
} else {
// x = k*m + a (k≥0)
long long maxK = (Ai - a) / m;
for (long long k = 0; k <= maxK; k++) {
long long newAi = Ai - (k * m + a);
long long newSG;
if (a == 0) {
newSG = (newAi / m) % 2;
} else {
newSG = ((newAi - a) / m) % 2;
}
if ((xorSum ^ currentSG ^ newSG) == 0) {
count++;
}
}
}
total = (total + count) % MOD;
}
cout << total << endl;
return 0;
}
有帮助，赞一个