A Yet Another Remainder The 2022 ICPC Asia Regionals Online Contest (II)

PTA | 程序设计类实验辅助教学平台

题目大意:有一个n位长的隐藏数x,从高位到低位依次标号为1到n,sum[i][j]表示从第i为开始每j位上的数的和,有q次询问,每次给出一个100以内除了5以外的质数p,问这个数%p等于多少

1<=t<=100;1<=n<=1e6;1<=i<=min(100,n);1<=j<=i;1<=q<=10

思路:对于x的第i位,可以将其写成x[i]*10^{n-i+1},x%p就相当于x[1]*10^{n-1}%p+x[2]*10^{n-2}%p+...+x[n]*10^{0}%p。

如果10^{n-i+1}%p=x,那么我们可以将每一项x[i]*10^{n-i+1}写成x[i]*(10^{n-i+1}-x),这样的每一项%p都等于0,那么原式子不等于0的部分就是10^{n-1}%p*x[1]+10^{n-2}%p*x[2]+...+10^{0}%p*x[n]。

然后又发现10^{n-i+1}%p是有循环节的,且循环节的长度是p-1,那么我们可以将上式拆成p-1个式子例如第一个式子是10^{n-1}%p*(x[1]+x[p]+x[2*p-1]+...),第二个式子就是10^{n-2}%p*(x[2]+x[p+1]+x[2*p]+...)。

每个式子里后面括号中的数都是题目中给出的即sum[p-1][第i位],所以可以在O(qtp)的时间复杂度内求出

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll sum[105][105];
void init()
{}
void solve()
{cin>>n;for(int i=1;i<=min(100,n);i++){for(int j=1;j<=i;j++){cin>>sum[i][j];}}int q;cin>>q;for(int i=1;i<=q;i++){ll mod;cin>>mod;vector<ll>m;ll x=1;for(int i=1;i<=mod-1;i++){//求出一个循环节m.push_back(x%mod);x=x*10%mod;}ll nn=n;ll ans=0;ll y=min(mod-1,nn);//如果p比n大,直接取sum的最后一行即可for(int i=1;i<=mod-1;i++){ll temp=nn%(mod-1);//第几位if(temp==0){temp=mod-2;}else{temp--;}ans=(ans+m[temp]*sum[y][i]%mod)%mod;nn--;}cout<<ans<<endl;}
}
int main()
{cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);int t;cin>>t;while(t--){solve();}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/127031.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

网络原理,了解xml, json,protobuffer的特点

目录 外卖服务器场景带入 大佬们通用的规范格式 一、&#x1f466; 外卖服务器场景 外面服务器沟通有很多模式——展示商家列表等等&#xff0c;只是其中一个&#xff0c;因此需要一个统一的规划了——不同应用程序&#xff0c;里面的自定义格式是不一样的&#xff0c;这样的…

前端组件库造轮子——Message组件开发教程

前端组件库造轮子——Message组件开发教程 前言 本系列旨在记录前端组件库开发经验&#xff0c;我们的组件库项目目前已在Github开源&#xff0c;下面是项目的部分组件。文章会详细介绍一些造组件库轮子的技巧并且最后会给出完整的演示demo。 文章旨在总结经验&#xff0c;开…

算法刷题记录-其他类型(LeetCode)

57 57. Insert Interval 思路 模拟 用指针去扫 intervals&#xff0c;最多可能有三个阶段&#xff1a; 不重叠的绿区间&#xff0c;在蓝区间的左边有重叠的绿区间不重叠的绿区间&#xff0c;在蓝区间的右边 逐个分析 不重叠&#xff0c;需满足&#xff1a;绿区间的右端&…

JVM之堆和方法区

目录 1.堆 1.1 堆的结构 1.1.1 新生代&#xff08;Young Generation&#xff09; 1.1.2 年老代&#xff08;Old Generation&#xff09; 1.1.3 永久代/元空间&#xff08;Permanent Generation/Metaspace&#xff09; 1.2 堆的内存溢出 1.3 堆内存诊断 1.3.1 jmap 1.3.2…

HTML5-3-表格

文章目录 属性边框属性标题跨行和跨列单元格边距 HTML 表格由 <table> 标签来定义。 tr&#xff1a;tr 是 table row 的缩写&#xff0c;表示表格的一行。td&#xff1a;td 是 table data 的缩写&#xff0c;表示表格的数据单元格。th&#xff1a;th 是 table header的缩…

黑盒测试中的决策表设计

前言 在软件开发中&#xff0c;测试是不可或缺的一个环节。其中&#xff0c;黑盒测试是一种比较常用的测试方法。它强调测试人员不需要知道程序内部结构&#xff0c;只需根据程序规格说明书来设计测试用例进行测试。本文将介绍黑盒测试中的一种决策表设计方法。 同时&#xf…

Games202(P6、P7)环境光照与PRT全局光照

P6、实时环境光照 RealTime Environment Mapping 不同于全局光照 (1) IBL 我的Blog&#xff1a; QT with OpenGL&#xff08;IBL-漫反射辐照&#xff09;IBL-镜面反射&#xff08;预滤波篇&#xff09;IBL-镜面反射&#xff08;LUT篇&#xff09;QT with OpenGL(IBL-镜面反…

mongodb数据库操作

1、启动mongodb /usr/local/mongodb/bin/mongod --dbpath /var/mongodb/data/--logpath /var/mongodb/logs/log.log &在mongodb启动命令中 --dbpath 指定mongodb的数据存储路径 --logpath 指定mongodb的日志存储路径 2、停止mongodb 第一步先进入mongo命令行模式 第二…

2023,软件测试人的未来在哪里?

2023年&#xff0c;IT行业出现空前的萧条&#xff0c;首先是年初一开始各大厂像着了魔似的不约而同的纷纷裁员、降薪、奖金包缩水&#xff0c;随之而来的是需求萎缩&#xff0c;HC减少或封锁等等。 而有幸未被列入裁员名单的在职人员&#xff0c;庆幸之余也心有余悸&#xff0…

R语言随机波动模型SV:马尔可夫蒙特卡罗法MCMC、正则化广义矩估计和准最大似然估计上证指数收益时间序列...

全文链接&#xff1a;http://tecdat.cn/?p31162 最近我们被客户要求撰写关于SV模型的研究报告&#xff0c;包括一些图形和统计输出&#xff08;点击文末“阅读原文”获取完整代码数据&#xff09;。 相关视频 本文做SV模型&#xff0c;选取马尔可夫蒙特卡罗法(MCMC)、正则化广…

App线上网络问题优化策略

在我们App开发过程中&#xff0c;网络是必不可少的&#xff0c;几乎很难想到有哪些app是不需要网络传输的&#xff0c;所以网络问题一般都是线下难以复现&#xff0c;一旦到了用户手里就会碰到很多疑难杂症&#xff0c;所以对于网络的监控是必不可少的&#xff0c;针对用户常见…

打字侠:一款专业的中文打字网站

打字侠第一个正式版发布啦&#xff01;&#xff01;&#xff01; 虽然离期望的样子还有一段路要走&#xff0c;不过能看到它正式发布&#xff0c;我还是很激动哟&#xff01; 打字侠是一款面向中学生和大学生的在线打字软件&#xff0c;它通过合理的课程设计和精美的图形界面帮…

力扣接雨水(解析)

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 示例 1&#xff1a; 输入&#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1] 输出&#xff1a;6 解释&#xff1a;上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] …

【狂神】SpringMVC笔记(一)之详细版

1.Restful 风格 概念&#xff1a; 实现方式&#xff1a; 使用PathVariable 在url相同的情况下&#xff0c;会根据请求方式的不同来执行不同的方法。 使用RestFull风格的好处&#xff1a;简洁、高效、安全 2、接受请求参数及数据回显 2.1、请求参数 方式一&#xff1a;这里…

FFmpeg入门之简单介绍

FFmpeg是什么意思: Fast Forward Moving Picture Experts Group ffmpeg相关文档: Documentation FFmpeg ffmpeg源码下载: https://git.videolan.org/git/ffmpeg.git https://github.com/FFmpeg/FFmpeg.git FFmpeg能做什么? 多种媒体格式的封装与解封装 : 1.多种音…

基于SSM的家居商城系统

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用JSP技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…

MySQL基础与库的基本操作

目录 1 MySQL基础一种存储解决方案SQL分类查看MySQL存储引擎 2 MySQL 库的操作数据库基本增删认识系统编码校验规则对数据库的影响数据库的查看与删除修改数据库数据库的备份与恢复查看连接情况 1 MySQL基础 一种存储解决方案 mysql本质是一种网络服务 mysql – 数据库服务的…

Stable DIffusion系统教程 | 局部重绘,增删修改的魔法棒

目录 1. 基本操作 1.1 步骤1 补充提示词 1.2 步骤2 绘制蒙版 1.3 步骤3 参数设置 2.局部重绘其他应用 2.1 手绘蒙版 2.2 删除某些东西 之前我们熟悉了AI绘画的各类模型&#xff0c;提示词写法&#xff0c;图像放大等技巧。但我们目前所有的操作都是针对整张图片的。 但…

栈的压入、弹出序列

⭐️ 题目描述 &#x1f31f; OJ链接&#xff1a;栈的压入、弹出序列 思路&#xff1a; 我们使用一个栈来模拟题目所给的压入、和弹出序列&#xff0c;若模拟成功则是真&#xff0c;模拟失败返回假。我们可以每次先从 pushV 入栈一个元素&#xff0c;在判断当前栈顶元素和 pop…

企业架构LNMP学习笔记10

1、Nginx版本&#xff0c;在实际的业务场景中&#xff0c;需要使用软件新版本的功能、特性。就需要对原有软件进行升级或重装系统。 Nginx的版本需要升级迭代。那么如何进行升级呢&#xff1f;线上服务器如何升级&#xff0c;我们选择稳定版本。 从nginx的1.14版本升级到ngin…