牛客挑战赛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 的每一位,直到两者均为 0while (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 = 500int main() {cin.tie(0)->sync_with_stdio(0); // 提高输入输出速度int n, k;cin >> n >> k;           // 输入数列长度 n 和进制 kfor(int i = 1; i <= n; i++) cin >> a[i]; // 输入每个点的特征值long long bace = 1, ans = 0; // bace 表示当前位的权重,初始为 1。ans 表示总权重和int f = 1; // 标记是否需要处理更高位,如果所有数都变成 0,f 就会变成 0while(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. 同一余数之间的组合贡献
  2. 不同余数之间的组合贡献

我们一段一段地分析这个代码。

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 * ik 进制下取余后的值。

  • 权重的影响:每一对组合的贡献还需要乘以当前位的权重 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),其中 i0k-1,而 ji+1k-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++) 计算的是不同余数ij)之间的组合贡献。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/473191.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

开源共建 | 长安链开发常见问题及规避

长安链开源社区鼓励社区成员参与社区共建&#xff0c;参与形式包括不限于代码贡献、文章撰写、社区答疑等。腾讯云区块链王燕飞在参与长安链测试工作过程中&#xff0c;深入细致地总结了长安链实际开发应用中的常见问题及其有效的规避方法&#xff0c;相关内容多次解答社区成员…

EWM 打印

目录 1 简介 2 后台配置 3 主数据 4 业务操作 1 简介 打印即输出管理&#xff08;output management&#xff09;利用“条件表”那一套理论实现。而当打印跟 EWM 集成到一起时&#xff0c;也需要利用 PPF&#xff08;Post Processing Framework&#xff09;那一套理论。而…

LLaMA-Factory全流程训练模型

&#x1f917;本文主要讲述在docker下使用LLaMA-Factory训练推理模型。 &#x1fae1;拉取镜像 首先需要启动docker&#xff0c;然后在终端中输入&#xff1a; docker run -tid --gpus all -p 8000:8000 --name LLM -e NVIDIA_DRIVER_CAPABILITIEScompute,utility -e NVIDIA…

WebSocket简易聊天室实现(有详细解释)

完整代码 Arata08/online-chat-demo 服务端: 1.编写配置类&#xff0c;扫描有 ServerEndpoint 注解的 Bean import org.springframework.context.annotation.Bean; import org.springframework.context.annotation.Configuration; import org.springframework.web.socket.s…

Excel超级处理器:高效实现2种批量生成二维码方式

在Excel数据处理中&#xff0c;二维码的批量生成是一个常见且重要的需求。借助Excel超级处理器这一强大的插件&#xff0c;用户可以轻松实现二维码的两种主要批量生成方式&#xff1a;直接在单元格中显示二维码图片&#xff0c;以及直接生成二维码图片并保存在文件夹中。超级处…

Linux Android 正点原子RK3568替换开机Logo完整教程

0.这CSDN是有BUG吗?大家注意:表示路径的2个点号全都变成3个点号啦! 接下来的后文中,应该是2个点都被CSDN变成了3个点: 1.将这两个 bmp 图片文件720x1280_8bit拷贝到内核源码目录下,替换内核源码中默认的 logo 图片。注意:此时还缺少电量显示图片 2.编译内核 make d…

性能高于Transformer模型1.7-2倍,彩云科技发布基于DCFormer架构通用大模型云锦天章

2017年&#xff0c;谷歌发布《Attention Is All You Need》论文&#xff0c;首次提出Transformer架构&#xff0c;掀开了人工智能自然语言处理&#xff08;NLP&#xff09;领域发展的全新篇章。Transformer架构作为神经网络学习中最重要的架构&#xff0c;成为后来席卷全球的一…

函数指针示例

目录&#xff1a; 代码&#xff1a; main.c #include <stdio.h> #include <stdlib.h>int Max(int x, int y); int Min(int x, int y);int main(int argc, char**argv) {int x,y;scanf("%d",&x);scanf("%d",&y);int select;printf(&q…

【书生大模型实战营 闯关材料】入门岛:第4关 玩转HF/魔搭/魔乐社区

2.1.2-2.1.3 InternLM 模型下载 模型下载 使用Hugging Face平台、魔搭社区平台&#xff08;可选&#xff09;和魔乐社区平台&#xff08;可选&#xff09;下载文档中提到的模型&#xff08;至少需要下载config.json文件、model.safetensors.index.json文件&#xff09;&#x…

Android - Pixel 6a 手机OS 由 Android 15 降级到 Android 14 操作记录

Pixel 6a 手机由 Android 14 升级到 Android 15了&#xff0c;但是由于一些原因又想降级回 Android 14&#xff0c; 能降吗&#xff1f;该怎么降级呢&#xff1f;本篇文章来记述实际操作过程&#xff0c;希望能给想做相同操作的人一些帮助。 答案当然是能降&#xff0c;而且我…

python-文件内容操作

文章目录 文件的介绍文件的理解文件操作基本知识文件对象属性与常用方法文件的读取文件的写入**上下文管理语句 with****读CSV文件**二维数据的存储从CSV格式的文件中读取数据将数据写入CSV格式的文件 读取Excel格式数据文件(pandas库)读取Excel格式数据文件(pandas库) 文件的介…

《操作系统 - 清华大学》3 -3:连续内存分配:内存碎片与分区的动态分配

文章目录 0. 概述1. 内存碎片问题2. 动态分配3. 首次适配算法4. 最优适配算法5. 最差适配算法 0. 概述 内存分配是操作系统管理过程中很重要的环节&#xff0c;首先需要考虑的是一块连续区域分配的过程&#xff0c;这个过程中会有很多问题&#xff0c;首先比较关注的一个问题是…

7.高可用集群架构Keepalived双主热备原理

一. 高可用集群架构Keepalived双主热备原理 (1)主机+备机keepalived配置(192.168.1.171) ! Configuration File for keepalivedglobal_defs {# 路由id:当前安装keepalived节点主机的标识符,全局唯一router_id keep_101 } #计算机节点(主机配置) vrrp_instance VI_1 {</

Notepad++的完美替代

由于Notepad的作者曾发表过可能在开发者代码中植入恶意软件的言论&#xff0c;他备受指责。在此&#xff0c;我向大家推荐一个Notepad的完美替代品——NotepadNext和Notepad--。 1、NotepadNext NotepadNext的特点&#xff1a; 1、跨平台兼容性 NotepadNext基于Electron或Qt…

【Chapter 3】Machine Learning Classification Case_Prediction of diabetes-XGBoost

文章目录 1、XGBoost Algorithm2、Comparison of algorithm implementation between Python code and Sentosa_DSML community edition(1) Data reading and statistical analysis(2)Data preprocessing(3)Model Training and Evaluation(4)Model visualization 3、summarize 1…

Linux(CentOS)安装达梦数据库 dm8

CentOS版本&#xff1a;CentOS 7&#xff0c;查看操作系统版本信息&#xff0c;请查阅 查看Linux内核版本信息 达梦数据库版本&#xff1a;dm8 一、获取 dm8 安装文件 1、下载安装文件 打开达梦官网&#xff1a;https://www.dameng.com/ 下载的文件 解压后的文件 2、上传安…

ReactPress与WordPress:两大开源发布平台的对比与选择

ReactPress与WordPress&#xff1a;两大开源发布平台的对比与选择 在当今数字化时代&#xff0c;内容管理系统&#xff08;CMS&#xff09;已成为各类网站和应用的核心组成部分。两款备受欢迎的开源发布平台——ReactPress和WordPress&#xff0c;各自拥有独特的优势和特点&am…

前后端请求响应

引入 在之前的例子中&#xff0c;我们编写了一个简单的web类&#xff0c;我们运行启动类&#xff0c;启动内嵌的tomcat后就可以在浏览器通过特定的路径访问tomcat中的应用程序。 但之前编写的程序仅仅是个简单的java类&#xff0c;其并未实现某个接口或继承某个类&…

Ubuntu24 上安装搜狗输入法

link 首先在终端中依次输入以下代码 sudo apt update sudo apt install fcitx 找到语言支持 在终端中依次输入 sudo cp /usr/share/applications/fcitx.desktop /etc/xdg/autostart/ sudo apt purge ibus 进入网页 搜狗输入法linux-首页​ shurufa.sogou.com/linux 找到刚才下…

Linux从0——1之shell编程4

声明&#xff01; 学习视频来自B站up主 **泷羽sec** 有兴趣的师傅可以关注一下&#xff0c;如涉及侵权马上删除文章&#xff0c;笔记只是方便各位师傅的学习和探讨&#xff0c;文章所提到的网站以及内容&#xff0c;只做学习交流&#xff0c;其他均与本人以及泷羽sec团队无关&a…