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

【题解】[GenshinOI Round 3] P9816 少项式复合幂

题目链接

分析

首先这题给了很大的提示信息 注意 m 和 p 的范围 , 很自然的想到可以先把所有可能的 f ( x ) f(x) f(x) 算出来.

思维误区

有些人在算完 f ( x ) f(x) f(x) 之后可能就会去思考找环的问题,然后一些码力弱的大佬就会祭掉.

在经过仔细的观察之后 (大多数人其实一眼就看出来了罢 , 可以发现最终答案的计算是符合结合律的,或者说具有传递性? 所以考虑倍增.

f a [ i ] [ j ] fa[i][j] fa[i][j] 表示 f 1 < < j ( i ) f_{1<<j}(i) f1<<j(i) 的值,初始时把 f [ i ] [ 0 ] f[i][0] f[i][0] 算出来,后面就可以直接倍增了.

Code

#include <bits/stdc++.h>
#define int long long
const int N = 1e5+10;using namespace std;
int m,q,p;
int ksm(int a, int b){int ans = 1;while(b){if(b&1){ans = ans * a % p;}a = a*a%p;b >>= 1;}return ans;
}
int a[30],b[30];
int f[N];
int get(int x){int ans = 0;for(int i = 1; i <= m; i++){ans = (ans + a[i]*ksm(x,b[i])%p) % p;}return ans;
}
bool vis[N];
int belong[N];
vector<int> e[N];
int fa[N][30]; 
void init(){for(int i = 0; i < p; i++){fa[i][0] = get(i);}for(int i = 1;i <= 25; i++){for(int j = 0; j < p; j++){fa[j][i] = fa[fa[j][i-1]][i-1];}}
}
signed main(){cin >> m >> q >> p;for(int i = 1; i<= m; i++){cin >> a[i] >> b[i];a[i] %= p;} init();while(q--){int x,y;cin >> x >> y;x %= p;for(int i = 25; i >= 0; i--){if((1 << i) <= y) x = fa[x][i],y -= (1<<i);}cout << x << endl;}return 0;
}

相关文章:

【题解】[GenshinOI Round 3] P9816 少项式复合幂

题目链接 分析 首先这题给了很大的提示信息 注意 m 和 p 的范围 , 很自然的想到可以先把所有可能的 f ( x ) f(x) f(x) 算出来. 思维误区 有些人在算完 f ( x ) f(x) f(x) 之后可能就会去思考找环的问题&#xff0c;然后一些码力弱的大佬就会祭掉. 在经过仔细的观察之后…...

手写数字识别--神经网络实验

实验源码自取&#xff1a; 神经网络实验报告源码.zip - 蓝奏云 上深度学习的课程&#xff0c;老师布置了一个经典的实验报告&#xff0c;我做了好久才搞懂&#xff0c;所以把实验报告放到CSDN保存&#xff0c;自己忘了方便查阅&#xff0c;也为其他人提供借鉴 由于本人是小白…...

双11消费遇冷?如何让消费回归心智原点

近一年来&#xff0c;小红书话题「重新养育自己」引热议。直面成长缺憾&#xff0c;不少人探寻解决方案&#xff0c;即像对待新生命般&#xff0c;不论是衣食住行还是心灵&#xff0c;重新关照自己。 借此&#xff0c;本期千瓜将锁定小红书热门话题背后的消费观转变&#xff0…...

一分钟了解:什么是Image Matting?

1. 基本概念 Image Matting是图像处理领域的一个基本任务&#xff0c;意为“图像背景抠出”或者“抠图”。这项任务在图像处理、影视制作领域广泛应用。比如&#xff0c;拍电影时常用的扣绿&#xff0c;就是演员在绿幕前面表演&#xff0c;后期再把人物抠出来放到一个新的背景…...

微信小程序 跳转客服页面

前言 小程序 用户反馈 没有页面设计 可以直接跳转小程序指定客服页面 <button class"contactBtn"open-type"contact" contact"handleContact" session-from"sessionFrom">...

10个简单增删改查的免费Spring Boot源代码项目

此页面包含用于学习目的的免费 Spring boot 项目列表。每个 Spring boot 项目的源代码都托管在 GitHub 存储库上&#xff0c;因此您可以免费下载或克隆源代码并亲身体验 Spring boot 框架。 1.员工管理应用程序&#xff08;ReactJS Spring Boot CRUD全栈应用程序&#xff09; …...

mysql数据表设计

命名 mysql表名的命名规范为表名可以用 t_ 、tb_的前缀&#xff0c;或者是业务模块前缀。比如t_order。 有些项目也会使用 tt_、tm_、 ts_ 等前缀&#xff0c;根据项目的习惯命名就好了。 主键&#xff1a; AUTO_INCREMENT 表示自增&#xff0c;UNSIGNED 表示无符号&#xf…...

pytorch复现4_Resnet

ResNet在《Deep Residual Learning for Image Recognition》论文中提出&#xff0c;是在CVPR 2016发表的一种影响深远的网络模型&#xff0c;由何凯明大神团队提出来&#xff0c;在ImageNet的分类比赛上将网络深度直接提高到了152层&#xff0c;前一年夺冠的VGG只有19层。Image…...

【数据库】形式化关系查询语言(一):关系代数Relational Algebra:基本运算、附加关系代数、扩展的关系代数

目录 一、关系代数Relational Algebra 1. 基本运算 a. 选择运算&#xff08;Select Operation&#xff09; b. 投影运算&#xff08;Project Operation&#xff09; 组合 c. 并运算&#xff08;Union Operation&#xff09; d. 集合差运算&#xff08;Set Difference Op…...

【计算机网络】计算机网络和因特网

一.基本术语介绍 端系统通过通信链路&#xff08;communication link&#xff09;和分组交换机&#xff08;packet switch&#xff09;连接到一起&#xff0c;连接这些端系统和分组交换机的物理媒体包括&#xff1a;同轴电缆&#xff0c;铜线&#xff0c;光纤和无线电频谱。而…...

JAVA面经整理(9)

一)什么是Spring&#xff1f;它有什么优点? spring是一款顶级的开源框架&#xff0c;他是包含了众多工具方法的IOC容器&#xff0c;Spring中包含了很多模块&#xff0c;比如说Spring-core&#xff0c;Spring-context&#xff0c;Spring-aop&#xff0c;Spring-web&#xff0c;…...

IPD(集成产品开发)模式下的产品研发流程

IPD&#xff08;集成产品开发&#xff09;涵盖了产品从创意提出到研发、生产、运营等&#xff0c;包含了产品开发到营销运营的整个过程。围绕产品&#xff08;或项目&#xff09;生命周期的过程的管理模式&#xff0c;是一套生产流程&#xff0c;更是时下国际先进的管理体系。I…...

Flutter GetX的使用

比较强大的状态管理框架 引入库&#xff1a; dependencies:get: ^4.6.6一.实现一个简单的demo 实现一个计数器功能 代码如下&#xff1a; import package:flutter/material.dart; import package:get/get.dart;void main() > runApp(const GetMaterialApp(home: Home()…...

【Amazon】AWS实战 | 快速发布安全传输的静态页面

文章目录 一、实验架构图二、实验涉及的AWS服务三、实验操作步骤1. 创建S3存储桶&#xff0c;存放网站网页2. 使用ACM建立域名证书3. 设置Cloudfront&#xff0c;连接S3存储桶✴️4. 设置Route53&#xff0c;解析域名服务5. 通过CLI工具上传网页更新内容【可选】 四、实验总结 …...

前后端登录的密码加密和解密

在一个典型的前后端应用中&#xff0c;前端对密码进行加密后传给后端&#xff0c;后端再进行解密或验证。这通常涉及前端加密、后端解密或验证的相互配合。下面是一个基本的流程&#xff1a; 前端加密&#xff1a; 前端可以使用各种加密库或算法对密码进行加密。常见的是使用哈…...

使用 Curl 和 DomCrawler 下载抖音视频链接并存储到指定文件夹

项目需求 假设我们需要从抖音平台上下载一些特定的视频&#xff0c;以便进行分析、编辑或其他用途。为了实现这个目标&#xff0c;我们需要编写一个爬虫程序来获取抖音视频的链接&#xff0c;并将其保存到本地文件夹中。 目标分析 在开始编写爬虫之前&#xff0c;我们需要了…...

取消Excel打开密码的两种方法

Excel设置了打开密码&#xff0c;想要取消打开密码是由两种方法的&#xff0c;今天分享这两种方法给大家。 想要取消密码是需要直到正确密码的&#xff0c;因为只有打开文件才能进行取消密码的操作 方法一&#xff1a; 是大家常见的取消方法&#xff0c;打开excel文件之后&a…...

多测师肖sir_高级金牌讲师_jmeter 反向代理录制脚本

jemeter自带的录制脚本功能&#xff0c;是利用代理服务器来进行录制的 1&#xff0c;新建一个线程组 2&#xff0c;新建一个代理服务器 右击工作台-添加-非测试元件-http代理服务器 3&#xff0c; 配置http代理服务器 端口&#xff1a; 默认为8888&#xff0c;可修改。但…...

网络取证-Tomcat-简单

题干&#xff1a; 我们的 SOC 团队在公司内部网的一台 Web 服务器上检测到可疑活动。为了更深入地了解情况&#xff0c;团队捕获了网络流量进行分析。此 pcap 文件可能包含一系列恶意活动&#xff0c;这些活动已导致 Apache Tomcat Web 服务器遭到破坏。我们需要进一步调查这一…...

3.Linux常用操作(传输、crontab定时、匹配日期删除文件等)

1. 服务器之间传输文件 1.1 传输文件到本服务器 scp -P 19622 -C dockeruser192.168.100.96:/home/dockeruser/lgr/lgr.dmp /home/dockeruser/lgr描述&#xff1a; 用dockeruser账号登录端口号为19622的192.168.100.96服务器&#xff0c;将此服务器的/home/dockeruser/lgr/l…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

FFmpeg avformat_open_input函数分析

函数内部的总体流程如下&#xff1a; avformat_open_input 精简后的代码如下&#xff1a; int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...