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

Educational Codeforces Round 7 F. The Sum of the k-th Powers 多项式、拉格朗日插值

news 来源：原创 2025/8/25 9:19:46

题目链接

题目大意

求 $(\sum_{i=1}^{n} i^k)$ $mod(10^9+7)$ .
数据范围： $\leq n \leq 10^9$ , $\leq k \leq 10^6$ .

思路

令 $f(n)=\sum_{i=1}^n=1^k+2^k+ \cdot \cdot \cdot +n^k$ .

观察题面可以发现，所求的答案是一个 $k + 1$ 次多项式，我们只需要找 $k + 2$ 个点带入拉格朗日插值公式中就可以计算出 $f (n)$ .

$n + 1$ 组点值 $x_i,y_i)$ ,得到的 $n$ 次多项式 $f (n)$ 的拉格朗日插值的方法为 : $f(x)=\sum_{i=0}^n y_i \prod_{j \neq i} \frac {x-x_j}{x_i-x_j}$ .

如果按照这个公式代进去硬算时间复杂度 $O(n^2)$ ,但我们可以选 $k + 2$ 个连续的点对这个式子进行简化。

我们把 $1$ 到 $k + 2$ 代入，对于分子， $\cdot \cdot \cdot (n-(i-1))$ 乘与 $\cdot \cdot \cdot (n-(i+1))$ ,这个可以 $O (k + 2)$ 预处理出来前缀积和后缀积， $O (1)$ 取用；对于分母是 $1$ 乘到 $(i - 1)$ 再乘上 $- 1$ 乘到 $(- (k + 2 - i)$ ,可以 $O (k + 2)$ 内预处理出 $1$ 到 $k + 2$ 阶乘的逆元， $O (1)$ 取用。

code

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pii pair<int, int>using namespace std;
const int N = 1e6 + 1000, mod = 1e9 + 7;
int pre[N], suf[N], infac[N];int ksm(int x, int k)
{int res = 1;while (k > 0){if (k & 1)res = res * x % mod;x = x * x % mod;k >>= 1;}return res;
}int inv(int x)
{return ksm(x, mod - 2);
}signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, k;cin >> n >> k;pre[0] = suf[k + 3] = infac[0] = 1;int fac = 1;for (int i = 1; i <= k + 2; ++i){pre[i] = pre[i - 1] * (n - i) % mod;fac = fac * i % mod;}infac[k + 2] = inv(fac);for (int i = k + 2; i >= 1; --i){suf[i] = suf[i + 1] * (n - i) % mod;if (i < k + 2)infac[i] = infac[i + 1] * (i + 1) % mod;}int y = 0, ans = 0;for (int i = 1; i <= k + 2; ++i){y = (y + ksm(i, k)) % mod;int tmp1 = pre[i - 1] * suf[i + 1] % mod;int tmp2 = infac[i - 1] * (((k + 2 - i) & 1) ? mod - infac[k + 2 - i] : infac[k + 2 - i]) % mod;ans = (ans + y * tmp1 % mod * tmp2 % mod) % mod;}cout << (ans + mod) % mod << '\n';return 0;
}

相关文章：

Educational Codeforces Round 7 F. The Sum of the k-th Powers 多项式、拉格朗日插值

题目链接题目大意求 ( ∑ i 1 n i k ) (\sum_{i1}^{n} i^k) (∑i1nik) m o d ( 1 0 9 7 ) mod(10^97) mod(1097) . 数据范围 ： 1 ≤ n ≤ 1 0 9 1 \leq n \leq 10^9 1≤n≤109 , 0 ≤ k ≤ 1 0 6 0 \leq k \leq 10^6 0≤k≤106 . 思路令 f ( n ) ∑ …...

编程日记 2025/8/25 9:19:46

学习笔记：利用OpenAI实现阅卷智能体

https://zhuanlan.zhihu.com/p/18047953492 ### 学习笔记：利用OpenAI实现阅卷智能体 #### 一、背景与需求在各类考试中，选择题、判断题、填空题的阅卷相对简单，只需对比答案与作答是否一致。然而，简答题的阅卷较为复杂&#xff…...

编程日记 2025/8/25 9:19:04

进程的简要介绍

一.进程 1.概念：担当分配系统资源的实体 2.进程内核数据结构对象自己的代码和数据或进程PCB(task_struct)自己的代码和数据注1：PCB：操作系统中描述进程的结构体 2.进程的所有属性均可在task_struct中找到，管理进程其实就是…...

编程日记 2025/8/25 9:17:50

每日一题——乘积最大子数组

乘积最大子数组问题详解问题描述示例约束条件问题分析难点分析解题思路代码实现代码说明测试用例测试用例 1测试用例 2测试用例 3 总结问题描述给定一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字&#x…...

编程日记 2025/8/25 9:19:45

HttpServletRequest 和 HttpServletResponse 区别和作用

一、核心作用对比对象HttpServletRequest（请求对象）HttpServletResponse（响应对象）本质客户端发给服务器的 HTTP 请求信息（输入）服务器返回客户端的 HTTP 响应信息（输出）生命周期一…...

编程日记 2025/8/25 9:19:06

黄昏时间户外街拍人像Lr调色教程，手机滤镜PS+Lightroom预设下载！

调色介绍黄昏时分有着独特而迷人的光线，使此时拍摄的人像自带一种浪漫、朦胧的氛围。通过 Lr 调色，可以进一步强化这种特质并根据不同的风格需求进行创作。Lr（Lightroom）作为专业的图像后期处理软件，提供了丰富的调色…...

编程日记 2025/8/25 9:17:54

Docker Desktop 安装与使用详解

目录 1. 前言2. Docker Desktop 安装2.1 下载及安装2.2 登录 Docker 账号2.3 进入 Docker Desktop 主界面 3. Docker 版本查看与环境检查3.1 查看 Docker Desktop 支持的 Docker 和 Kubernetes 版本3.2 检查 Docker 版本 4. Docker Hub 和常用镜像管理方式4.1 使用 Docker Hub4…...

编程日记 2025/8/24 20:35:53

DeepSeek-R1与全光网络的医疗技术协同场景深度分析

一、DeepSeek-R1与全光网络的技术协同场景 1. 实时诊疗与数据交互 1. 实时诊疗与数据交互 1.1 场景示例分析高带宽需求：医疗影像，尤其是CT和MRI影像，通常具有高分辨率和大数据量，要求医疗系统具备超高带宽来实时传输这些数据。全光网络，特别是基于华为F5G的解决方案，…...

编程日记 2025/8/25 9:17:27

热图回归（Heatmap Regression）

热图回归（Heatmap Regression）是一种常用于关键点估计任务的方法，特别是在人体姿态估计中。它的基本思想是通过生成热图来表示某个关键点在图像中出现的概率或强度。以下是热图回归的主要特点和工作原理：主要特点热图表示：每个关键点对应一个热图，热图中的每个像素值…...

编程日记 2025/8/25 9:17:50

模型微调-基于LLaMA-Factory进行微调的一个简单案例

模型微调-基于LLaMA-Factory进行微调的一个简单案例 1. 租用云计算资源2. 拉取 LLaMa-Factory3. 安装依赖环境4. 启动 LLaMa-Factory 界面5. 从 Huggingface 下载模型6. 模型验证7. 模型微调 1. 租用云计算资源以下示例基于 AutoDL 云计算资源。在云计算平台选择可用的云计…...

编程日记 2025/8/25 9:16:12

shell的模拟实现 ─── linux第16课

在shell的命令行中输入命令,会有两种执行命令的途径 shell自己执行 shell创建子进程(fork ,exit ,waitpid,exec) ,子进程去执行 shell自己执行的命令是自建命令(bulit command) 子进程执行的是非自建命令第一版只能维护命令行参数表创建子进程, 执行非内建命令我们先创…...

编程日记 2025/8/25 9:16:09

Luna——为游戏添加音效

1、在GameManager中声明 public AudioSource audiosource; public AudioClip normalClip; public AudioClip battleClip; 2、在GameManager资产中挂载“Audio Source”组件，并将该组件挂载到资产脚本中的声明对象这就可以根据不同场景的需要切换背景音乐了&#x…...

编程日记 2025/8/24 16:00:54

计算机视觉算法实战——老虎个体识别（主页有源码）

✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连 ✨ ✨个人主页欢迎您的访问 ✨期待您的三连✨ 1. 领域介绍老虎个体识别是计算机视觉中的一个重要应用领域，旨在通过分析老虎的独特条纹图案，自动识别和区…...

编程日记 2025/8/25 9:16:58

技术速递｜GitHub Copilot Agent 模式（预览版）介绍

作者：Isidor Nikolic 翻译：Alan Wang GitHub Copilot Agent 模式（预览版）是 AI 辅助编码的最新进化。它作为一个自主的编程助手，可以根据你的指令执行多步骤的编码任务——分析代码库、读取相关文件、提出文件编辑建议…...

编程日记 2025/8/25 9:19:05

《安富莱嵌入式周报》第351期：DIY半导体制造，工业设备抗干扰提升方法，NASA软件开发规范，小型LCD在线UI编辑器，开源USB PD电源，开源锂电池管理

周报汇总地址：嵌入式周报 - uCOS & uCGUI & emWin & embOS & TouchGFX & ThreadX - 硬汉嵌入式论坛 - Powered by Discuz! 视频版： https://www.bilibili.com/video/BV16C95YEEZs 《安富莱嵌入式周报》第351期：DIY半导体…...

编程日记 2025/8/25 9:17:26

CSS—补充：CSS计数器、单位、@media媒体查询

目录 1. CSS计数器嵌套计数器： 对列表元素： 2.单位绝对长度： 相对长度： 3.media媒体查询 1. CSS计数器 CSS 计数器就像“变量”。变量值可以通过 CSS 规则递增（将跟踪它们的使用次数）。如需使用…...

编程日记 2025/8/25 9:19:05

Phi-4-multimodal：图、文、音频统一的多模态大模型架构、训练方法、数据细节

Phi-4-Multimodal 是一种参数高效的多模态模型，通过 LoRA 适配器和模式特定路由器实现文本、视觉和语音/音频的无缝集成。训练过程包括多阶段优化，确保在不同模式和任务上的性能，数据来源多样，覆盖高质量网络和合成数据。它的设计…...

编程日记 2025/8/25 9:17:27

Leetcode::将水果放入篮子II（c++）

3477. 将水果放入篮子 II 提示给你两个长度为 n 的整数数组，fruits 和 baskets，其中 fruits[i] 表示第 i 种水果的数量，baskets[j] 表示第 j 个篮子的容量。你需要对 fruits 数组从左到右按照以下规则放置水果： 每种水果必…...

编程日记 2025/8/25 9:17:50

【C语言系列】字符函数和字符串函数

字符函数和字符串函数一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2strlen函数模拟实现四、strcpy的使用和模拟实现4.1strcpy函数4.2strcpy函数的模拟实现五、strcat的使用和模拟实现5.1strcat函数5.2strcat函数的模拟实现六、strcmp的使用…...

编程日记 2025/8/25 9:17:51

【计算机网络】深入解析 HTTP 协议的概念、工作原理和通过 Fiddler 抓包查看 HTTP 请求/响应的协议格式

网络原理— HTTP 1. 什么是HTTP? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议： HTTP 往往是基于传输层的 TCP 协议实现的 (HTTP1.0,HTTP1.1,HTTP2.0 均为TCP,HTTP3基于UDP实现) 我们平时打开一个网站，就是通过HTTP协议来…...

编程日记 2025/8/25 9:17:00

InDraw6.2.3 | 甾体、核苷、黄酮类化合物实现简称命名

导语当化学家对着屏幕输入"2-amino-1,9-dihydro-6H-purin-6-one"时，隔壁生物学家可能正在搜索"鸟嘌呤"；这种命名差异如同"火星文"与"地球语"的碰撞。现在，鹰谷InDraw 6.2.3版带着53种多环化合物的…...

编程日记 2025/8/25 9:17:51

AI Copilot——维新派的贾维斯，守旧派的墓志铭（程序员视角）

6500万年前的那颗陨石好像要落下来了这一段时间，伴随着claude sonnet 3.7的发布以及cursor，windsurf 等一众AI智能编辑器的涌现，社区的programming自媒体坐不住了，有一个观点已经快要溢出屏幕：程序员这个岗位要黄&a…...

编程日记 2025/8/25 9:19:03

c++ 接口/多态

目录接口的通用定义特点： C 中的接口接口的作用接口与抽象类的区别什么是多态？ 多态的类型 1. 编译时多态 2. 运行时多态多态的实现原理注意事项在编程中，接口（Interface） 是一个抽象概念&#xff…...

编程日记 2025/8/25 9:17:51

【大模型学习】第十二章大模型获取智能机制

目录引言 1. 模型架构 Transformer架构层次结构和层数 2. 训练数据 3. 大规模训练 4. 迁移学习与微调 4.1 微调步骤 5. 机制实例自注意力机制多头注意力机制总结引言随着深度学习的发展，特别是大型预训练模型（大模型）的出…...

编程日记 2025/8/25 9:17:27

神经网络|(十四)|霍普菲尔德神经网络-Hebbian训练

【1】引言前序学习进程中，除了对基本的神经网络知识进行了学习，还掌握了SOM神经网络原理，文章链接包括且不限于： 神经网络|(十一)|神经元和神经网络-CSDN博客神经网络|(十二)|常见激活函数-CSDN博客神经网络|(十三)|SOM神经…...

编程日记 2025/8/24 11:40:46

华为鸿蒙系统全景解读：从内核设计到生态落地的技术革命

华为鸿蒙系统全景解读：从内核设计到生态落地的技术革命前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，可以分享一下给大家。点击跳转到网站。 https://www.captainbed.cn/ccc 文章目录华为鸿蒙系统全景解读&#x…...

编程日记 2025/8/16 10:05:32

基于大数据的Steam游戏数据分析可视化推荐系统

【大数据】🎮 项目名：游戏分析神器，用代码探析游戏世界——《基于大数据的Steam游戏分析与智能推荐系统》（完整系统源码开发笔记详细部署教程）✅ 目录一、项目简介二、项目界面展示三、项目视频展示一、项目简介 &a…...

编程日记 2025/8/22 9:34:22

将长上下文大语言模型研究从输入转向输出

将长上下文大语言模型研究从输入转向输出摘要: 近年来，长上下文大语言模型（LLMs）的研发主要集中在处理更长的输入文本上，这使得模型在理解长篇内容时取得了显著进步。然而，生成长篇输出的研究却相对被忽视&#xff…...

编程日记 2025/8/23 5:20:57

Dify 开源大语言模型应用开发平台使用（二）

文章目录说明Dify 使用报告1. 应用创建——专业的锂电池相关知识解答1.1 平台简介1.2 创建应用2. 知识库、工作流、变量、节点与编排节点详解2.1 知识库管理2.2 工作流配置2.3 变量管理2.4 节点与编排节点3. 测试和调试3.1 单元测试3.2 日志与监控3.3 实时调试3.4 性能测试总结…...

编程日记 2025/8/18 5:45:27

CarPlanner：用于自动驾驶大规模强化学习的一致性自回归轨迹规划

25年2月来自浙大和菜鸟网络的论文“CarPlanner: Consistent Auto-regressive Trajectory Planning for Large-scale Reinforcement Learning in Autonomous Driving”。轨迹规划对于自动驾驶至关重要，可确保在复杂环境中安全高效地导航。虽然最近基于学习的方法&a…...

编程日记 2025/8/22 17:43:34

K8s面试题总结（十一）

1.如何优化docker镜像的大小？ 使用多阶段构建（multi-stage build）选择更小的基础镜像（如alpine）减少镜像层数，合并RUN命令 2.请解释Docker中的网络模式（如bridge,host,none) Bridge&#xff…...

编程日记 2025/8/24 4:34:10

Android Telephony 四大服务和数据网络控制面数据面介绍

在移动通信和Android系统中，涉及的关键概念和服务以及场景案例说明如下：一、概念（一）Android Telephony 的四大服务介绍Telephony Data 与 Android Data 的四大服务在Android系统中，与电话（Telephony）和移动数据（Data）相关的核心服务主要包括以下四类： 1. Tele…...

编程日记 2025/8/19 21:47:10

一文讲懂Go语言如何使用配置文件连接数据库

一文讲懂Go语言如何使用配置文件连接数据库 viper1. viper简介2. viper 读取.toml配置文件定义Go语言结构体编写与Go语言结构体对应的.toml配置文件定义初始化函数定义get函数连接数据库1. 定义数据库对象2. 定义初始化函数3. 定义 get 函数4. 定义 main 函数, 连接数据库配置…...

编程日记 2025/8/23 23:02:03

Jmeter使用介绍

文章目录前言Jmeter简介安装与配置JDK安装与配置JMeter安装与配置打开JMeter方式一方式二设置Jmeter语言为中文方法一（仅一次性）方法二(永久设置成中文) Jmeter文件常用目录元件与组件元件组件元件的作用域元件的执行顺序第一个案例添加线程组添加 H…...

编程日记 2025/8/25 1:24:37

MES机联网4：文档资料

目录信息 MES机联网1：技术方案MES机联网2：采集网关MES机联网3：管理后台MES机联网4：文档资料 MQ接入文档 1、建立连接 mqtt连接地址: 192.168.0.138 mqtt端口: 1883 mqtt用户名：admin mqtt密码：123456 …...

编程日记 2025/8/23 18:01:42

豆包大模型 MarsCode AI 刷题专栏 001

001.找单独的数难度：易问题描述在一个班级中，每位同学都拿到了一张卡片，上面有一个整数。有趣的是，除了一个数字之外，所有的数字都恰好出现了两次。现在需要你帮助班长小C快速找到那个拿了独特数字卡片的同学手上…...

编程日记 2025/8/21 1:09:57

常用无功功率算法的C语言实现（二）

0 前言尽管数字延迟法和积分移相法在不间断采样的无功功率计算中得到了广泛应用，但它们仍存在一些固有缺陷。对于数字延迟法而言，其需要额外存储至少1/4周期的采样点，在高采样频率的场景下，这对存储资源的需求不可忽视。而积分移相法虽然避免了额外的存储开销，但为了抑制…...

编程日记 2025/8/20 20:53:49

23种设计模式简介

一、创建型（5种） 1.工厂方法总店定义制作流程，分店各自实现特色披萨（北京店-烤鸭披萨，上海店-蟹粉披萨） 2.抽象工厂套餐工厂（家庭装含大披萨薯条，情侣装含双拼披萨红酒&#…...

编程日记 2025/8/24 15:33:22

开发vue小游戏：数字华龙道

一、游戏介绍 1、历史背景数字华容道脱胎于传统华容道，后者源自三国时期“曹操败走华容道”的故事。传统玩法是通过移动不同形状的木块，帮助“曹操”从出口逃脱。而数字华容道将棋子替换为数字，目标是通过滑动方块，将乱…...

编程日记 2025/8/22 22:50:19

electron的通信方式（三种）

文章目录一、渲染进程向主进程发送消息二、渲染进程向主进程发送消息并异步获取结果三、主进程向渲染进程发送消息 electron的主要是主线程和渲染线程之间的通信，简单记录一下三种通信方式一、渲染进程向主进程发送消息利用ipcRenderer.send()和ipcMain.on()方法…...

编程日记 2025/8/20 14:06:57

MapReduce技术概述**

** MapReduce是一种并行计算框架，最初由Google开发，后来被Apache开源。它是一种分布式计算模型，能够处理大规模数据集，解决复杂的计算问题。MapReduce技术在数据处理和分析领域广泛应用，尤其是在大数据处理中。 MapR…...

编程日记 2025/8/22 1:05:46

ubuntu挂载固态硬盘

Ubuntu 中挂载位于 /dev/sdc1 的固态硬盘，可以按照以下步骤操作： 步骤 1：确认分区信息首先，确保设备 /dev/sdc1 存在且已正确分区： sudo fdisk -l /dev/sdc # 查看分区表 lsblk # 确认分区路…...

编程日记 2025/8/25 6:44:29

同为科技智能PDU在数据中心场景的应用与解决方案

数据中心当前处于一个快速发展和技术变革的特殊时期，全新的人工智能应用正在重塑整个世界，为社会带来便捷的同时，也为数据中心的发展带来了新的机遇和挑战。智能算例的爆发式增长，对数据中心提出了大算力、高性能的新需求&#xf…...

编程日记 2025/8/24 10:05:36

golang学习笔记——go语言安装及系统环境变量设置

文章目录 go语言安装go envgo getgoproxy测试安装 Go 插件安装 Go 插件依赖工具参考资料用户环境变量和系统环境变量用户环境变量系统环境变量示例设置环境变量的步骤设置用户环境变量设置系统环境变量验证环境变量总结 2024年最火的5大Go框架1. Gin：高并发接口的“…...

编程日记 2025/8/22 20:46:24

云服务器Linux安装Docker

系统要求 Docker 官方建议将 Docker 运行在 Linux系统上，当然也可以在其他平台运行，本篇博客只介绍在 Linux 系统上的安装方法。 Docker 运行在 CentOS7.X 版本以上，本文使用阿里云 ECS 云服务器 CentOS 7.4 版本。 Docker 需要安装在 64 …...

编程日记 2025/8/21 18:15:11

2025DNS二级域名分发PHP网站源码

安装教程 1.程序必须使用PHP8.1 2.将扩展ixed.8.1.lin放入/www/server/php/81/lib/php/extensions/no-debug-non-zts-20210902 3.打开宝塔→软件商店→PHP8.1→配置文件 4.放入：extensionixed.8.1.lin 5.重启PHP8.1 6.新建站点（mysql5.6-5.7andPHP8.1&a…...

编程日记 2025/8/25 9:00:29

审批流AntV框架蚂蚁数据可视化X6饼图（附注释）

大家好，这次使用的是AntV的蚂蚁数据可视化X6框架，类似于审批流的场景等，代码如下： X6框架参考网址：https://x6.antv.vision/zh/examples/showcase/practices#bpmn 可以进入该网址，直接复制下方代码进行调试…...

编程日记 2025/8/20 2:34:41

git 添加额外的远程仓库 URL

要使用 git branch -a 查看 net-next 远程仓库中的所有分支，请按照以下步骤操作： 步骤 1: 确保已添加 net-next 远程仓库如果尚未添加 net-next 远程仓库，请运行以下命令： git remote add net-next git://git.kernel.org/pub/s…...

编程日记 2025/8/23 5:21:07

Qt中实现多个QMainWindow同时显示

在Qt中实现多个QMainWindow同时显示，可通过以下方法实现： 一、直接显示多个实例必须使用new创建堆对象，避免栈对象因作用域结束被销毁‌。 int main(int argc, char *argv[]) {QApplication a(argc, argv);// 创建两个独立的主窗口QMainW…...

编程日记 2025/8/23 2:14:47

在ArcMap中通过Python编写自定义工具（Python Toolbox）实现点转线工具

文章目录一、需求二、实现过程2.1、创建Python工具箱（.pyt）2.2、使用catalog测试代码2.3、在ArcMap中使用工具三、测试一、需求通过插件的形式将点转线功能嵌入ArcMap界面，如何从零开始创建一个插件，包括按钮的添加、工具的实…...

编程日记 2025/8/20 14:09:14