HDOJ 4506 小明系列故事——师兄帮帮忙(腾讯专场,快速幂)

2023-12-13 19:48

本文主要是介绍HDOJ 4506 小明系列故事——师兄帮帮忙(腾讯专场,快速幂),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

http://acm.hdu.edu.cn/showproblem.php?pid=4506

小明系列故事——师兄帮帮忙

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 5563    Accepted Submission(s): 1510


Problem Description
小明自从告别了ACM/ICPC之后,就开始潜心研究数学问题了,一则可以为接下来的考研做准备,再者可以借此机会帮助一些同学,尤其是漂亮的师妹。这不,班里唯一的女生又拿一道数学题来请教小明,小明当然很高兴的就接受了。不过等他仔细读题以后,发现自己也不会做,这下小明囧了:如果回复说自己不懂,岂不是很没面子?
  所以,他现在私下求你帮忙解决这道题目,题目是这样的:
  给你n个数字,分别是a1,a2,a3,a4,a5……an,这些数字每过一个单位时间就会改变,假设上一个单位时间的数字为a1’,a2’,a3’……an’,那么这个单位时间的数字a[i] = a[i - 1]’ * K(i == 1的时候a[1] = a[n]’ * K),其中K为给定的系数。
  现在的问题就是求第t单位时间的时候这n个数字变成了什么了?由于数字可能会很大,所以只要你输出数字对10^9 + 7取余以后的结果。

Input
输入数据第一行是一个正整数T,表示有T组测试数据;
  每组数据有两行,第一行包含输入三个整数n, t, k,其中n代表数字个数,t代表第t个单位时间,k代表系数;第二行输入n个数字ai,代表每个数字开始的时候是多少。

   [Technical Specification]
  T <= 100
  1 <= n <= 10 ^ 4
  0 <= t <= 10 ^ 9  其中 t = 0 表示初始状态
  1 <= k <= 10 ^ 9
  1 <= ai<= 10 ^ 9

Output
对于每组数据请输出第t单位时间后这n个数字变成了什么,输出的时候 每两个数字之间输出一个空格,行末不要输出多余的空格,具体见样例。

Sample Input
  
2 3 2 5 1 2 3 3 0 5 1 2 3

Sample Output
  
50 75 25 1 2 3

Source
2013腾讯编程马拉松初赛第一场(3月21日)

思路:

这个题目卡的时间是最长的,可能之前思路是错的,卡在了找最终系数的问题上,

最后只能够 ko blog.。

最后附上自己的不完善的思路。

AC CODE:

#include<stdio.h>
#include<cstring>
#include<algorithm>
#define HardBoy main()
#define ForMyLove return 0;
using namespace std;
const int MYDD = 11030;
const int MOD = 1e9+7;int PowQuick(int a, int n, int mod) {int ans = 1;while(n > 0) {if(n&1) ans = ((long long)ans*a) % mod;/*KILL BUG -> ((long long)(ans*a)) */a = ((long long)a*a) % mod;/*注意范围溢出*//*KILL BUG -> ((long long)(a*a))*/n >>= 1;}return (int)ans;
}int HardBoy {int tt;scanf("%d", &tt);while(tt--) {int a[MYDD], n, t, k;scanf("%d %d %d", &n, &t, &k);for(int j = 1; j <= n; j++) {scanf("%d", &a[j]);}int ans[MYDD];int getpow = PowQuick(k,t, MOD);for(int i = 1; i <= n; i++) {/*note*/ans[i] = ((long long)a[i]*getpow)%MOD;ans[i] = (int)ans[i];}t = t%n;int x = n-t+1;if(x > n) x = x%n;for(int j = x; j <= n; j++) {if(j == x) printf("%d",ans[j]);else printf(" %d",ans[j]);}for(int j=1; j < x; j++)printf(" %d",ans[j]);printf("\n");}ForMyLove
}

错误 ->


CODE WRONG :

#include<stdio.h>
#include<cstring>
#include<algorithm>
#define HardBoy main()
#define ForMyLove return 0;
using namespace std;
const int MYDD = 11030;
const int MOD = 1e9+7;int PowQuick(int a, int n, int mod) {int ans = 1;while(n > 0) {if(n&1) ans = (ans*a) % mod;a = (long long)(a*a) % mod;/*注意范围溢出*/n >>= 1;}return ans;
}int HardBoy {int tt;scanf("%d", &tt);while(tt--) {int a[MYDD], n, t, k;scanf("%d %d %d", &n, &t, &k);int getpow = PowQuick(k, t, MOD);for(int j = 1; j <= n; j++) {scanf("%d", &a[j]);}int ans[MYDD];t = t%n;for(int j = 1; j <= n; j++) {int biao = j+n%t;if(j == n) {int biao = (j+n%t)%n;if(n == t) biao = n;ans[j] = ((a[biao] % MOD) * getpow) % MOD;} else {ans[j] = ((a[biao] % MOD) * getpow) % MOD;}printf("ans[%d] -> j:%d \n", j, biao);}for(int j = 1; j < n; j++) {printf("%d ", ans[j]);}printf("%d\n", ans[n]);}ForMyLove
}
/*
6
3 1 5
1 2 3*/


这篇关于HDOJ 4506 小明系列故事——师兄帮帮忙(腾讯专场,快速幂)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/489748

相关文章

一文详解如何在idea中快速搭建一个Spring Boot项目

《一文详解如何在idea中快速搭建一个SpringBoot项目》IntelliJIDEA作为Java开发者的‌首选IDE‌,深度集成SpringBoot支持,可一键生成项目骨架、智能配置依赖,这篇文... 目录前言1、创建项目名称2、勾选需要的依赖3、在setting中检查maven4、编写数据源5、开启热

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2

8种快速易用的Python Matplotlib数据可视化方法汇总(附源码)

《8种快速易用的PythonMatplotlib数据可视化方法汇总(附源码)》你是否曾经面对一堆复杂的数据,却不知道如何让它们变得直观易懂?别慌,Python的Matplotlib库是你数据可视化的... 目录引言1. 折线图(Line Plot)——趋势分析2. 柱状图(Bar Chart)——对比分析3

一文教你Java如何快速构建项目骨架

《一文教你Java如何快速构建项目骨架》在Java项目开发过程中,构建项目骨架是一项繁琐但又基础重要的工作,Java领域有许多代码生成工具可以帮助我们快速完成这一任务,下面就跟随小编一起来了解下... 目录一、代码生成工具概述常用 Java 代码生成工具简介代码生成工具的优势二、使用 MyBATis Gen

使用animation.css库快速实现CSS3旋转动画效果

《使用animation.css库快速实现CSS3旋转动画效果》随着Web技术的不断发展,动画效果已经成为了网页设计中不可或缺的一部分,本文将深入探讨animation.css的工作原理,如何使用以及... 目录1. css3动画技术简介2. animation.css库介绍2.1 animation.cs

SpringBoot快速搭建TCP服务端和客户端全过程

《SpringBoot快速搭建TCP服务端和客户端全过程》:本文主要介绍SpringBoot快速搭建TCP服务端和客户端全过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录TCPServerTCPClient总结由于工作需要,研究了SpringBoot搭建TCP通信的过程

一文教你Python如何快速精准抓取网页数据

《一文教你Python如何快速精准抓取网页数据》这篇文章主要为大家详细介绍了如何利用Python实现快速精准抓取网页数据,文中的示例代码简洁易懂,具有一定的借鉴价值,有需要的小伙伴可以了解下... 目录1. 准备工作2. 基础爬虫实现3. 高级功能扩展3.1 抓取文章详情3.2 保存数据到文件4. 完整示例

快速修复一个Panic的Linux内核的技巧

《快速修复一个Panic的Linux内核的技巧》Linux系统中运行了不当的mkinitcpio操作导致内核文件不能正常工作,重启的时候,内核启动中止于Panic状态,该怎么解决这个问题呢?下面我们就... 感谢China编程(www.chinasem.cn)网友 鸢一雨音 的投稿写这篇文章是有原因的。为了配置完

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

利用Python快速搭建Markdown笔记发布系统

《利用Python快速搭建Markdown笔记发布系统》这篇文章主要为大家详细介绍了使用Python生态的成熟工具,在30分钟内搭建一个支持Markdown渲染、分类标签、全文搜索的私有化知识发布系统... 目录引言:为什么要自建知识博客一、技术选型:极简主义开发栈二、系统架构设计三、核心代码实现(分步解析