当前位置: 首页 > news >正文

COCI 2021-2022 #1 - Set 题解

思路

我们将原题中的数的每一位减一,此时问题等价。

下面的异或都是在三进制下的异或。(相当于不进位的加法)

我们考虑原题中的条件,对于每一位,如果相同,则异或值为 0 0 0,如果为 1 1 1 2 2 2 3 3 3 的排列,则异或值也为 0 0 0

于是我们设 C k C_k Ck 表示有没有 k k k 这个数, a n s = ∑ i ⊕ j ⊕ k = 0 c i ⋅ c j ⋅ c k ans=\sum_{i\oplus j\oplus k = 0} c_i\cdot c_j\cdot c_k ans=ijk=0cicjck,则答案为 a n s − n 6 \frac{ans - n}{6} 6ansn

其中 a n s ans ans 可以用 FWT 求,具体实现可以看我的博客。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, k, len = 1;
LL ans;
complex <double> a[1000005];
const complex <double> w = {-0.5, 0.5 * sqrt(3)}, w2 = {-0.5, -0.5 * sqrt(3)};
int in() {char ch = getchar();int s = 0;while (ch < '0' || ch > '9')ch = getchar();while (ch <= '9' && ch >= '0')s = s * 3 + ch - '1', ch = getchar();return s;
}
void FWT(complex <double> *f, int flag) {for (int mid = 1; mid < len; mid = mid * 3) {for (int i = 0; i < len; i = i + mid * 3) {for (int j = i; j < i + mid; j++) {complex <double> t0 = f[j], t1 = f[j + mid], t2 = f[j + mid * 2];if (flag == 1) {f[j] = t0 + t1 + t2;f[j + mid] = t0 + t1 * w + t2 * w2;f[j + mid * 2] = t0 + t1 * w2 + t2 * w;}else {f[j] = t0 + t1 + t2;f[j + mid] = t0 + t1 * w2 + t2 * w;f[j + mid * 2] = t0 + t1 * w + t2 * w2;double t;t = f[j].real(), f[j].real(t / 3);t = f[j + mid].real(), f[j + mid].real(t / 3);t = f[j + mid * 2].real(), f[j + mid * 2].real(t / 3);t = f[j].imag(), f[j].imag(t / 3);t = f[j + mid].imag(), f[j + mid].imag(t / 3);t = f[j + mid * 2].imag(), f[j + mid * 2].imag(t / 3);}}}}
}
int main() {scanf("%d%d", &n, &k);for (int t = 0; t < k; t++)len = len * 3;for (int i = 0; i < n; i++)a[in()].real(1);FWT(a, 1);for (int i = 0; i < len; i++)a[i] = a[i] * a[i] * a[i];FWT(a, -1);ans = a[0].real() + 0.5;printf("%lld\n", (ans - n) / 6);return 0;
}

相关文章:

COCI 2021-2022 #1 - Set 题解

思路 我们将原题中的数的每一位减一&#xff0c;此时问题等价。 下面的异或都是在三进制下的异或。&#xff08;相当于不进位的加法&#xff09; 我们考虑原题中的条件&#xff0c;对于每一位&#xff0c;如果相同&#xff0c;则异或值为 0 0 0&#xff0c;如果为 1 1 1&a…...

分享40个极具商业价值的chatGPT提问prompt

原文&#xff1a;分享40个极具商业价值的chatGPT提问prompt | 秋天的童话博客 1、分析并改善定价策略 提示: "分析我当前的[插入产品或服务]定价策略。提出改进建议&#xff0c;并帮助我制定新的定价策略&#xff0c;以最大化利润和客户满意度。" Analyze and Imp…...

一文搞懂到底什么是元宇宙

一、背景 2021年&#xff0c;“元宇宙”是科技界的开端。 2021”元宇宙”这个词在Facebook更名后被点燃了&#xff0c;无疑是21世纪科技界最爆的起点。各式各样的定义、解读都出现了&#xff0c;有人说它是炒作&#xff0c;甚至是骗局&#xff0c;但也有人说它就是互联网的未…...

【重拾C语言】六、批量数据组织(四)线性表—栈和队列

目录 前言 六、批量数据组织——数组 6.1~3 数组基础知识 6.4 线性表——分类与检索 6.5~7 数组初值&#xff1b;字符串、字符数组、字符串数组&#xff1b;类型定义 typedef 6.8 线性表—栈和队列 6.8.1 栈&#xff08;Stack&#xff09; 全局变量 isEmpty() isFull…...

力扣刷题-哈希表-一个字符串是否能够由另一个字符串中的字符组成

383 赎金信 给你两个字符串&#xff1a;ransomNote 和 magazine &#xff0c;判断 ransomNote 能不能由 magazine 里面的字符构成。 如果可以&#xff0c;返回 true &#xff1b;否则返回 false 。 magazine 中的每个字符只能在 ransomNote 中使用一次。ransomNote 和 magazin…...

Android使用AOP切面编程

在Android应用程序中&#xff0c;AOP可以被用于许多不同的场景&#xff0c;例如日志记录、权限控制、性能分析等。下面是一个简单的例子&#xff0c;说明如何在Android应用程序中使用AOP切面编程。 首先&#xff0c;我们需要在应用程序中引入AspectJ库。我们可以使用Gradle来完…...

Flutter学习笔记

此篇文章用来记录学习Flutter 和 Dart 相关知识 零.Dart基本数据类型 Dart 是一种静态类型的编程语言&#xff0c;它提供了一系列基本数据类型&#xff0c;用于存储和操作不同种类的数据。以下是 Dart 中的一些基本数据类型以及它们的详细介绍&#xff1a; 1. 整数类型&#…...

软件生命周期中的概念设计和详细设计的主要任务是什么

基础概念 在软件生命周期中&#xff0c;概念设计和详细设计是软件设计阶段中的两个重要环节。 概念设计阶段的主要任务是从业务需求出发&#xff0c;将系统的基本概念、主要功能和关键特性进行抽象和定义。概念设计旨在确定系统的整体架构和关键模块&#xff0c;包括以下主要…...

大数据学习(2)Hadoop-分布式资源计算hive(1)

&&大数据学习&& &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 承认自己的无知&#xff0c;乃是开启智慧的大门 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4dd;支持一下博>主哦&#x…...

深入探究HTML表单与JavaScript的关系

深入探究HTML表单与JavaScript的关系 引言 HTML表单是网页中数据收集的重要工具&#xff0c;而JavaScript则充当着这些数据的处理者和控制者的角色。二者之间的关系非常紧密&#xff0c;共同构成了现代Web应用中用户交互的基础。在这篇博客中&#xff0c;我们将详细地解析HTM…...

关于Jupyter notebook 创建python3 时进去不能重命名问题及不能编程问题

首先写这篇博客时&#xff0c;已经被这个问题折磨了三天&#xff0c;看了很多博客&#xff0c;其实解决这个问题的关键就是要么没有下pyzmq或者等级太高&#xff0c;要么等级太低&#xff0c;首先我会按照我思路来。 问题如图&#xff1a; 1.自动换行 2.不能重命名 我的解决办…...

一些可以用代码绘制流程图的工具

代码绘制流程图的工具有很多,以下是一些常用的工具: Mermaid:Mermaid 是一个基于 Markdown 的图表语言,可以生成各种类型的图表,包括流程图、时序图、甘特图等。Mermaid 可以使用 JavaScript 或 TypeScript 进行编写,可以通过 Node.js 运行。Graphviz:Graphviz 是一个开…...

Centos中清除因程序异常终止,导致的残留的Cache/buff_drop_caches命令---linux工作笔记063

我这里因为nifi程序背压设置的不合理,导致,内存和CPU消耗过高,系统崩溃,但是重启NIFI以后,发现 对应的执行top命令,看到,系统的buff/cache 依然没有减少,说明内存被浪费了,残留在这里没有被回收. 用这个办法执行这个命令; linux会自动触发清理,但是只有在内存不够用的时候才会…...

Element-UI的使用——表格el-table组件去除边框、滚动条设置、隔行变色、去除鼠标悬停变色效果(基于less)

// Element-ui table表格去掉所有边框,如下&#xff1a; // 备注&#xff1a;若去掉所有边框&#xff0c;可自行将头部边框注释掉即可 // 该样式写在style scoped外面在el-table 中添加class"customer-table"类名 //去掉每行的下边框/deep/ .el-table td.el-table__c…...

python的一些知识点

之前自学过python&#xff0c;学了一些基本语法&#xff0c;但忘得厉害。最近&#xff0c;在努力地写代码&#xff0c;在学代码&#xff0c;写代码中学习python&#xff0c;为此记录一些关于python的知识点。...

QML 带框最大化显示方法

1.QML窗口最大化很多会给出如下方法: visibility: "FullScreen" 此方法不好的方面是没有最大化&#xff0c;最小化&#xff0c;关闭按钮 2.通过showMaximized() 方法可以满足我们需求:在onCompleted 方法中执行 实现的效果如下:...

conda命令大全

conda list 查看环境中已经安装了的软件包 conda list --name your_env_name(虚拟环境名) 查看某个环境下的包 conda config --show 查看现有源 conda env list 或者 conda info -e 查看当前存在那些虚拟环境 conda update conda 更新至最新的conda版本 conda update [pac…...

国庆要闻回顾 | OpenAI 拟研发 AI 手机;9月以太坊上NFT销售量创2021年2月以来最低记录...

国庆期间区块链行业要闻回顾&#xff1a;产业方面&#xff0c;全国区块链行业产教融合共同体在雄安新区成立&#xff0c;巴西推出基于区块链的数字身份证&#xff0c;瑞银集团在以太坊上推出代币化货币市场基金试点&#xff0c;NASA拟在月球设立区块链数据中心以保存国家机密资…...

国家开放大学 模拟试题 训练

试卷代号&#xff1a;2136 管理会计 参考 试题 一、单项选择题&#xff08;每小题1分&#xff0c;共20分&#xff09; 1.管理会计依靠各种功能来助力企业战略&#xff0c;下列哪项是管理会计的核心功能( )。 A.评价功能 B.预测功能 C.决策功能…...

【GIT版本控制】--常见问题与解决方案

一、修复损坏的仓库 修复损坏的Git仓库可能是面临的一种问题&#xff0c;这通常是由于文件损坏、存储介质问题或不正确的操作等原因引起的。以下是一些修复损坏的Git仓库的常见问题和解决方案&#xff1a; 常见问题&#xff1a; 无法执行Git命令&#xff1a;当尝试运行Git命令…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍

文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结&#xff1a; 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析&#xff1a; 实际业务去理解体会统一注…...

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...