牛客挑战赛77
#include <iostream>
// 函数 kXOR：计算两个数在 k 进制下的异或和
// 参数：
// a: 第一个正整数
// b: 第二个正整数
// k: 进制基数
// 返回值：
// 两数在 k 进制下的异或和（十进制表示）
long long kXOR(long long a, long long b, long long k) {
long long result = 0; // 存储最终结果的变量
long long multiplier = 1; // 用于记录 k 的权重（对应 k^0, k^1, k^2 ...）
// 循环处理 a 和 b 的每一位，直到两者均为 0
while (a > 0 || b > 0) {
// 提取 a 和 b 当前最低位的 k 进制数字
long long digitA = a % k; // a 的最低位
long long digitB = b % k; // b 的最低位
// 计算当前位的“异或”结果，实际上是 k 进制下的无进位加法
long long xorDigit = digitA + digitB;
// 如果当前位的和大于或等于 k，则减去 k，模拟 k 进制的循环特性
if (xorDigit >= k) {
xorDigit -= k;
}
// 将当前位的结果按权重加到最终结果中
result += xorDigit * multiplier;
// 移除处理过的最低位，准备处理更高位
a /= k;
b /= k;
// 更新权重为当前位的 k 次幂
multiplier *= k;
}
// 返回最终计算的异或和
return result;
}
int main() {
long long k, A, B; // 定义进制 k 和两个正整数 A, B
// 从标准输入读取三个正整数
std::cin >> k >> A >> B;
// 调用 kXOR 函数计算两数在 k 进制下的异或和
long long weight = kXOR(A, B, k);
// 输出计算结果
std::cout << weight << std::endl;
return 0; // 程序正常结束
}
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10; // 数组 a 的最大长度为 2000010
int mod = 1e9 + 7; // 模数 10^9 + 7，用于防止结果溢出
long long a[N]; // 存储特征值的数组
long long cnt[505]; // 统计每一位上某个余数出现的次数，最大进制 k = 500
int main() {
cin.tie(0)->sync_with_stdio(0); // 提高输入输出速度
int n, k;
cin >> n >> k; // 输入数列长度 n 和进制 k
for(int i = 1; i <= n; i++) cin >> a[i]; // 输入每个点的特征值
long long bace = 1, ans = 0; // bace 表示当前位的权重，初始为 1。ans 表示总权重和
int f = 1; // 标记是否需要处理更高位，如果所有数都变成 0，f 就会变成 0
while(f) {
f = 0; // 假设当前处理的是最后一位
memset(cnt, 0, sizeof cnt); // 清空 cnt 数组，重新统计当前位
// 统计当前位的余数分布
for(int i = 1; i <= n; i++) {
cnt[a[i] % k]++; // 统计当前数在 k 进制下最低位的余数
a[i] /= k; // 去掉最低位，为下一次循环做准备
if(a[i]) f = 1; // 如果去掉最低位后仍不为 0，则需要继续处理更高位
}
// 计算当前位的贡献
for(int i = 0; i < k; i++) {
// 计算同一余数（i）之间的组合的贡献
if(cnt[i] >= 2)
ans = (ans + cnt[i] * (cnt[i] - 1) / 2 % mod * (2 * i % k) % mod * bace) % mod;
// 计算不同余数之间的组合的贡献
for(int j = i + 1; j < k; j++) {
ans = (ans + cnt[i] * cnt[j] % mod * ((i + j) % k) % mod * bace) % mod;
}
}
// 更新当前位的权重，进入下一位（相当于乘以 k）
bace = (bace * k) % mod;
}
cout << ans << '\n'; // 输出结果
return 0;
}
着重解释这一段代码
for (int i = 0; i < k; i++) {
// 计算同一余数（i）之间的组合的贡献
if (cnt[i] >= 2) {
ans = (ans + cnt[i] * (cnt[i] - 1) / 2 % mod * (2 * i % k) % mod * bace) % mod;
}
// 计算不同余数之间的组合的贡献
for (int j = i + 1; j < k; j++) {
ans = (ans + cnt[i] * cnt[j] % mod * ((i + j) % k) % mod * bace) % mod;
}
}这段代码的目的是计算每个位上所有数的贡献值，根据它们在 k 进制下的余数分布，进行不同余数之间和相同余数之间的组合计算。具体来说，它计算了两种类型的组合贡献：
- 同一余数之间的组合贡献。
- 不同余数之间的组合贡献。
我们一段一段地分析这个代码。
1. 循环遍历所有可能的余数
for (int i = 0; i < k; i++) {
该循环遍历所有可能的余数 i（从 0 到 k-1）。cnt[i] 记录了在当前位上余数为 i 的数的个数。
2. 计算同一余数（i）之间的组合贡献
if (cnt[i] >= 2) {
ans = (ans + cnt[i] * (cnt[i] - 1) / 2 % mod * (2 * i % k) % mod * bace) % mod;
}
cnt[i] 表示余数为 i 的数的个数。如果 cnt[i] >= 2，说明有两个或更多的数具有相同的余数，可以进行组合。
-
组合的数量：从
cnt[i]个相同余数的数中，选择两个数来进行组合。组合数是C(cnt[i], 2)，即cnt[i] * (cnt[i] - 1) / 2。 -
贡献的计算：每一对相同余数的组合贡献为
(2 * i) % k，即这对数的贡献为2 * i在k进制下取余后的值。 -
权重的影响：每一对组合的贡献还需要乘以当前位的权重
bace，因为权重随着位数增加而逐渐变大。
所以，更新 ans 的公式为：
ans = (ans + cnt[i] * (cnt[i] - 1) / 2 % mod * (2 * i % k) % mod * bace) % mod;
3. 计算不同余数（i, j）之间的组合贡献
for (int j = i + 1; j < k; j++) {
ans = (ans + cnt[i] * cnt[j] % mod * ((i + j) % k) % mod * bace) % mod;
}
-
这个嵌套的循环遍历了所有不同余数的对
(i, j)，其中i从0到k-1，而j从i+1到k-1。确保每对(i, j)都是不同的。 -
组合的数量：对于每对不同的余数
(i, j)，组合数是cnt[i] * cnt[j]，即选择一个余数为i的数和一个余数为j的数。 -
贡献的计算：每一对不同余数的组合贡献为
(i + j) % k，即两者余数之和的k进制下的值。 -
权重的影响：每一对组合的贡献还需要乘以当前位的权重
bace。所以，更新
ans的公式为：
ans = (ans + cnt[i] * cnt[j] % mod * ((i + j) % k) % mod * bace) % mod;
-
这一步计算了所有不同余数的数对的贡献。
4. 总结：
- 第一部分
if (cnt[i] >= 2)计算的是同一余数（i）之间的组合贡献，它考虑的是从同余数的数中选择两个的情况。 - 第二部分
for (int j = i + 1; j < k; j++)计算的是不同余数（i和j）之间的组合贡献。
原文地址：https://blog.csdn.net/ke_wu/article/details/143808058
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！