sdut2605 A^X mod P 山东省第四届ACM省赛(打表,快速幂模思想,哈希)

本文主要是介绍sdut2605 A^X mod P 山东省第四届ACM省赛(打表,快速幂模思想,哈希),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文出自:http://blog.csdn.net/svitter


题意:

f(x) = K, x = 1

f(x) = (a*f(x-1) + b)%m , x > 1

求出( A^(f(1)) + A^(f(2)) + A^(f(3)) + ...... + A^(f(n)) ) modular P.

1 <= n <= 10^6

0 <= A, K, a, b <= 10^9

1 <= m, P <= 10^9

本题目的关键在于大幂的分解和。。你要这样想,因为不停的求A的幂,所以肯定把算过的保存下来最合适。

打表。(- -)每次都是打表,shit。

把f分解为 fix * k + j 的形式,f就是f(x)的简称。(哈希)

然后关键是fix怎么整,多少合适。我觉得33333合适。为啥?

因为10^9 / 33333 =30000数组不大。然后余数也在33333之内,其好,那就它吧。

然后就用普通的幂模相乘打表就可以f[i] = (f[i-1] * a)mod p,这是个简单的例子,a和p没有实际含义。

这个题目我在做的时候蛋疼到二分法动态打表,但是超空间,因为不停的递归调用造成了超空间。。但是我觉得如果能够实现。。用栈的方法,应该会更加节省时间。因为用到的才计算。如果有不同的意见,请回复我,谢谢。


AC代码:

//============================================================================
// Name        : math.cpp
// Author      : Vit
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cmath>using namespace std;
#define lln long long int
#define fix 33333//num
lln n, A, K, a, b, m, P;//A^f f = fix * k + j
//    f = dp1 * k + dp2lln dpk[30001];
lln dpj[33334];void init()
{int i, j;//init hashdpj[1] = A;dpj[0] = dpk[0] = 1;for(i = 2; i <= 33333; i++)dpj[i] = (dpj[i-1] * A) % P;dpk[1] = dpj[33333];for(j = 1; j <= 30000; j ++)dpk[j] = (dpk[j-1] * dpk[1]) % P;
}void ace()
{//work pit;int i, t, c;lln ans, f;scanf("%d", &t);for(c = 1; c <= t; c++){scanf("%lld%lld%lld%lld%lld%lld%lld",&n, &A, &K, &a, &b, &m, &P);//initinit();f = K;ans = 0;for(i = 0; i < n; i++){ans = (ans + dpk[f/fix] * dpj[f % fix]) % P;f = (a * f + b) % m;}printf("Case #%d: %lld\n", c, ans);}
}int main()
{ace();return 0;
}


这篇关于sdut2605 A^X mod P 山东省第四届ACM省赛(打表,快速幂模思想,哈希)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

Java如何将文件内容转换为MD5哈希值

《Java如何将文件内容转换为MD5哈希值》:本文主要介绍Java如何将文件内容转换为MD5哈希值的实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java文件内容转换为MD5哈希值一个完整的Java示例代码代码解释注意事项总结Java文件内容转换为MD5

使用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渲染、分类标签、全文搜索的私有化知识发布系统... 目录引言:为什么要自建知识博客一、技术选型:极简主义开发栈二、系统架构设计三、核心代码实现(分步解析