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

CF914G Sum the Fibonacci

CF914G Sum the Fibonacci

洛谷Sum the Fibonacci

题目大意

给你一个长度为 n n n的数组 s s s,定义五元组 ( a , b , c , d , e ) (a,b,c,d,e) (a,b,c,d,e)是合法的当且仅当:

  • 1 ≤ a , b , c , d , e ≤ n 1\leq a,b,c,d,e\leq n 1a,b,c,d,en
  • ( s a ∣ s b ) & s c & ( s d ⊕ s e ) = 2 i , i ∈ Z (s_a|s_b)\& s_c\& (s_d\oplus s_e)=2^i,i\in Z (sasb)&sc&(sdse)=2i,iZ
  • s a & s b = 0 s_a\& s_b=0 sa&sb=0

对于所有合法的五元组 ( a , b , c , d , e ) (a,b,c,d,e) (a,b,c,d,e),求 ∑ f ( s a ∣ s b ) × f ( s c ) × f ( s d ⊕ s e ) \sum f(s_a|s_b)\times f(s_c)\times f(s_d\oplus s_e) f(sasb)×f(sc)×f(sdse)

f 0 = 0 , f 1 = 1 , f i = f i − 1 + f i − 2 ( i ≥ 2 ) f_0=0,f_1=1,f_i=f_{i-1}+f_{i-2}(i\geq 2) f0=0,f1=1,fi=fi1+fi2(i2)

输出答案对 1 0 9 + 7 10^9+7 109+7取模后的值。

1 ≤ n ≤ 1 0 6 , 0 ≤ s i < 2 17 1\leq n\leq 10^6,0\leq s_i<2^{17} 1n106,0si<217


题解

前置知识:快速沃尔什变换( F W T FWT FWT

i = s a & s b , j = s c , k = s d ⊕ s e i=s_a\&s_b,j=s_c,k=s_d\oplus s_e i=sa&sb,j=sc,k=sdse

题意即求

∑ p ∑ i & j & k = 2 p f i × f j × f k × ( ∑ s a ∣ s b = i , s a & s b = 0 1 ) × ( ∑ s c = j 1 ) × ( ∑ s d ⊕ s e = k 1 ) \sum\limits_p\sum\limits_{i\& j\& k=2^p}f_i\times f_j\times f_k\times (\sum\limits_{s_a|s_b=i,s_a\& s_b=0}1)\times (\sum\limits_{s_c=j}1)\times (\sum\limits_{s_d\oplus s_e=k}1) pi&j&k=2pfi×fj×fk×(sasb=i,sa&sb=01)×(sc=j1)×(sdse=k1)

p i p_i pi表示 i i i在数组 s s s中出现的次数,那么

( ∑ s a ∣ s b = i , s a & s b = 0 1 ) = ∑ x ∣ y = i , x & y = 0 p x × p y (\sum\limits_{s_a|s_b=i,s_a\& s_b=0}1)=\sum\limits_{x|y=i,x\& y=0}p_x\times p_y (sasb=i,sa&sb=01)=xy=i,x&y=0px×py

( ∑ s c = j 1 ) = p j (\sum\limits_{s_c=j}1)=p_j (sc=j1)=pj

( ∑ s d ⊕ s e = k 1 ) = ∑ i ⊕ j = k p i × p j (\sum\limits_{s_d\oplus s_e=k}1)=\sum\limits_{i\oplus j=k}p_i\times p_j (sdse=k1)=ij=kpi×pj

第二个式子很好求。对于第一个式子和第三个式子,用 F W T FWT FWT的子集卷积和异或卷积,分别用 O ( m log ⁡ 2 m ) , O ( m log ⁡ m ) O(m\log^2 m),O(m\log m) O(mlog2m),O(mlogm)的时间复杂度求出,其中 m = 2 17 m=2^{17} m=217

code

#include<bits/stdc++.h>
using namespace std;
int n,x,cnt[1<<17];
long long ans=0,f[1<<17],s[1<<17],t[20][1<<17],a[1<<17],b[1<<17],c[1<<17],v[1<<17];
const long long mod=1e9+7,ny2=5e8+4;
void pt(long long *w){for(int i=0;i<1<<17;i++) w[i]=s[i];
}
void fwt_or(long long *w,int fl){for(int s=2;s<=1<<17;s<<=1){int mid=s>>1;for(int v=0;v<1<<17;v+=s){for(int i=0;i<mid;i++){w[v+mid+i]=(w[v+mid+i]+fl*w[v+i]+mod)%mod;}}}
}
void fwt_and(long long *w,int fl){for(int s=2;s<=1<<17;s<<=1){int mid=s>>1;for(int v=0;v<1<<17;v+=s){for(int i=0;i<mid;i++){w[v+i]=(w[v+i]+fl*w[v+mid+i]+mod)%mod;}}}
}
void fwt_xor(long long *w,int fl){for(int s=2;s<=1<<17;s<<=1){int mid=s>>1;for(int v=0;v<1<<17;v+=s){for(int i=0;i<mid;i++){long long t1=w[v+i],t2=w[v+mid+i];w[v+i]=(t1+t2)%mod;w[v+mid+i]=(t1-t2+mod)%mod;if(fl==-1){w[v+i]=w[v+i]*ny2%mod;w[v+mid+i]=w[v+mid+i]*ny2%mod;}}}}
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&x);++s[x];}f[0]=0;f[1]=1;cnt[1]=1;for(int i=2;i<1<<17;i++){cnt[i]=cnt[i-(i&(-i))]+1;f[i]=(f[i-1]+f[i-2])%mod;}for(int i=0;i<1<<17;i++){t[cnt[i]][i]=s[i];}for(int i=0;i<=17;i++){fwt_or(t[i],1);}for(int i=0;i<=17;i++){for(int j=0;j<=i;j++){for(int k=0;k<1<<17;k++){v[k]=(v[k]+t[j][k]*t[i-j][k]%mod)%mod;}}fwt_or(v,-1);for(int j=0;j<(1<<17);j++){if(cnt[j]==i) a[j]=v[j];v[j]=0;}}pt(b);pt(c);fwt_xor(c,1);for(int i=0;i<1<<17;i++){c[i]=c[i]*c[i]%mod;}fwt_xor(c,-1);for(int i=0;i<1<<17;i++){a[i]=a[i]*f[i]%mod;b[i]=b[i]*f[i]%mod;c[i]=c[i]*f[i]%mod;}fwt_and(a,1);fwt_and(b,1);fwt_and(c,1);for(int i=0;i<1<<17;i++){v[i]=a[i]*b[i]%mod*c[i]%mod;}fwt_and(v,-1);for(int i=1;i<1<<17;i<<=1){ans=(ans+v[i])%mod;}printf("%lld",ans);return 0;
}

相关文章:

CF914G Sum the Fibonacci

CF914G Sum the Fibonacci 洛谷Sum the Fibonacci 题目大意 给你一个长度为 n n n的数组 s s s&#xff0c;定义五元组 ( a , b , c , d , e ) (a,b,c,d,e) (a,b,c,d,e)是合法的当且仅当&#xff1a; 1 ≤ a , b , c , d , e ≤ n 1\leq a,b,c,d,e\leq n 1≤a,b,c,d,e≤n ( …...

Shell基础入门实战

写在前面 好久没在项目内做自动化了&#xff0c;主要是现阶段在项目内做自动化收益不大&#xff0c;最近开发做batch run的正好缺人&#xff0c;我看了一下代码&#xff0c;就是通过代码读取jar包和远程服务器连接&#xff0c;然后通过shell脚本&#xff0c;向数据库插入数据&a…...

如何进行微服务的技术选型?

本文首发自「慕课网」&#xff0c;想了解更多IT干货内容&#xff0c;程序员圈内热闻&#xff0c;欢迎关注"慕课网"&#xff01; 作者&#xff1a;陈于吉吉|慕课网讲师 随着这几年微服务的火爆&#xff0c;在平时的工作或者技术交流中&#xff0c;我们总能听到哪家公…...

Vue电商项目--应用开发详解

vue-cli脚手架初始化项目 首先&#xff0c;页面上新建一个文件夹。然后打开命令端口 vue create app 选择Default ([Vue 2] babel, eslint) 然后把项目拖拽到vscode中。项目目录看一下 脚手架项目的目录 node_modules:放置项目依赖的地方 public:一般放置一些共用的静态资源&a…...

Lvs负载均衡

系列文章目录 文章目录 系列文章目录一、集群1.集群2. 二、LVS1.LVS简介2.负载均衡的结构3.Lvs调度算法 总结 一、集群 1.集群 集群群集 cluster由多台主机构成的一个整体&#xff0c;提供一个放问入口(IP或域名)&#xff0c;集群中的多台主机都干一件事提供一样的服务 负载均…...

JAVAWeb08-手动实现 Tomcat 底层机制+ 自己设计 Servlet

1. 前言 先看一个小案例&#xff0c; 引出对 Tomcat 底层实现思考 1.1 完成小案例 ● 快速给小伙伴完成这个小案例 0. 我们准备使用 Maven 来创建一个 WEB 项目, 老师先简单给小伙伴介绍一下 Maven 是什么, 更加详细的使用&#xff0c;我们还会细讲, 现在先使用一把 先创建…...

非监督学习简单介绍

文章目录 非监督学习简单介绍聚类K-meansHierarchical聚类DBSCAN 降维PCAt-SNE 其他非监督学习技术结论 非监督学习简单介绍 非监督学习是机器学习中的一种方法&#xff0c;其目标是基于数据的内在结构和关系&#xff0c;从而在无标签数据中识别样本的潜在结构和模式。非监督学…...

香港科技大学有什么好的专业?

香港科技大学创办于1991年10月&#xff0c;是一所坐落于香港清水湾半岛的公立研究型大学。大学设有4个学院&#xff1a;工学院、理学院、人文社会科学学院和工商管理学院&#xff0c;还设有2个研究院&#xff1a;香港科技大学公共政策和行政研究生院和香港科技大学霍英东研究院…...

【两个月算法速成】day04

本文以收录专题刷题记录 目录 24. 两两交换链表中的节点 题目链接 思路 代码 19. 删除链表的倒数第 N 个结点 题目链接 思路-双指针 代码 面试题 02.07. 链表相交 题目链接 思路 代码 24. 两两交换链表中的节点 题目链接 力扣 思路 建议使用虚拟节点&#xff0…...

【Python】实战:生成无关联单选问卷 csv《压疮风险评估表》

目录 一、适用场景 二、业务需求 三、Python 文件 &#xff08;1&#xff09;创建文件 &#xff08;2&#xff09;代码示例 四、csv 文件 一、适用场景 实战场景&#xff1a; 问卷全部为单选题问卷问题全部为必填问题之间无关联关系每个问题的答案分数不同根据问卷全部问…...

rsync 远程删除文件

rsync 远程删除文件 rsync是一个强大的远程数据同步工具,它不仅可以实现远程文件复制,也可以实现远程文件删除。 要使用rsync实现远程删除文件,可以使用如下命令: bash rsync -avz --delete usernameremotehost:/path/to/files /path/to/local/dir这个命令的主要参数: -a:归…...

LinkedBlockingQueue原理

1. 基本的入队出队 public class LinkedBlockingQueue<E> extends AbstractQueue<E>implements BlockingQueue<E>, java.io.Serializable {static class Node<E> {E item;/*** 下列三种情况之一* - 真正的后继节点* - 自己, 发生在出队时* - null, 表…...

哈希表题目:网格照明

文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目 标题和出处 标题&#xff1a;网格照明 出处&#xff1a;1001. 网格照明 难度 6 级 题目描述 要求 在 n n \texttt{n} \times \texttt{n} nn 的二维网格 grid \texttt{grid}…...

Python多线程爬虫为何效率低下?解析原因并提高爬虫速度的方法

目录 一、知识点二、多线程语法GIL单线程多线程单线程多线程 最后的惊喜 一、知识点 线程&#xff08;Thread&#xff09;也叫轻量级进程&#xff0c;是操作系统能够进行运算调度的最小单位&#xff0c;它被包含在进程之中&#xff0c;是进程中的实际运作单位。线程自己不拥有…...

Python 标准方形信号定义(完美实现)

之前我们介绍了如何定义一个标准的正弦信号,这里我们做一下延申,简单说明一下如何定义一个方形函数。 方形信号表达式 square signal = g ( t ) = sign [ sin ⁡ ( 2 π f t +...

[Daimayuan] 走不出的迷宫(C++,图论,DP)

有一个 H H H 行 W W W 列的迷宫&#xff08;行号从上到下是 1 − H 1−H 1−H&#xff0c;列号从左到右是 1 − W 1−W 1−W&#xff09;&#xff0c;现在有一个由 . 和 # 组成的 H 行 W 列的矩阵表示这个迷宫的构造&#xff0c;. 代表可以通过的空地&#xff0c;# 代表不…...

【LeetCode: 1416. 恢复数组 | 暴力递归=>记忆化搜索=>动态规划 】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…...

centos7查看磁盘io

1.查看所使用到的命令为iostat&#xff0c;centos7没有自带iostat&#xff0c;需要安装一下 2.安装iostat命令 yum -y install sysstat 3.使用iostat命令 iostat %user&#xff1a;表示用户空间进程使用 CPU 时间的百分比 %nice&#xff1a;表示用户空间进程以降低优先级的…...

浅析低代码开发的典型应用构建场景v

在数字经济蓬勃发展的大势之下&#xff0c;企业软件开发人员供给不足、开发速度慢、开发成本高、数字化和智能化成效不明显等问题日益凸出&#xff0c;阻碍了企业的数字化转型。 而近年来&#xff0c;低代码的出现推动了经济社会的全面提效&#xff0c;也成为人才供求矛盾的润…...

3 连续模块(二)

3.5 零极点增益模块 在控制系统设计和分析中&#xff0c;常用的函数包括 传递函数&#xff08;tf&#xff09;、零极点&#xff08;zpk&#xff09;和状态空间&#xff08;ss&#xff09;函数 传递函数&#xff08;tf&#xff09;&#xff1a;用于表示线性时不变系统的输入输出…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

边缘计算医疗风险自查APP开发方案

核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

BLEU评分:机器翻译质量评估的黄金标准

BLEU评分&#xff1a;机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域&#xff0c;衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标&#xff0c;自2002年由IBM的Kishore Papineni等人提出以来&#xff0c;…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL

ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...

边缘计算网关提升水产养殖尾水处理的远程运维效率

一、项目背景 随着水产养殖行业的快速发展&#xff0c;养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下&#xff0c;而且难以实现精准监控和管理。为了提升尾水处理的效果和效率&#xff0c;同时降低人力成本&#xff0c;某大型水产养殖企业决定…...