当前位置: 首页 > 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…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...