首页 / MYSQL / NOIP2014D2T3解方程Hash大法好

NOIP2014D2T3解方程Hash大法好

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了NOIP2014D2T3解方程Hash大法好，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2256字，纯文字阅读大概需要4分钟。

内容图文

题目大意：给定高次方程an*x^n...a1*x^1a0*x^0=0 求[1,m]区间内有多少个整数根 ai=10^10000，m=100W 懒得高精，考场上写的long double乱搞……30分打底50分顶天QAQ 当我终于搞定了各种非官方数据之后，我只能长跪大地，手捧鲜花，仰望上苍高喊：哈希大法好！

题目大意：给定高次方程an*x^n+...+a1*x^1+a0*x^0=0 求[1,m]区间内有多少个整数根

ai<=10^10000，m<=100W

懒得高精，考场上写的long double乱搞……30分打底50分顶天QAQ

当我终于搞定了各种非官方数据之后，我只能长跪大地，手捧鲜花，仰望上苍高喊：哈希大法好！

首先阿贝尔在200年前告诉我们五次以上方程没有求根公式于是我们只能枚举1~m 这个是100W

然后100W再加上1W位的精度都不用运算直接就是跪…… 怎么办呢QAQ

哈希大法好！

令f(x)=an*x^n+...+a1*x^1+a0*x^0 易知若f(x)=0 则f(x) mod p=0

反之如果f(x) mod p=0 那么我们基本可以得出f(x)=0 p比较靠谱的时候碰撞率极低

所以我们把所有的ai都对p取模然后对于每个解O(n)验证即可

这样是O(m*n)的可以拿到70分 p比较靠谱的话不会挂

那么100分怎么办呢？

哈希大法好！

我们很容易就会发现f(x+p) mod p=f(x) mod p

于是我们选择一个小一些的p，预处理出0~p-1所有的f(x)，然后超过p的取模即可

但是p不够大会挂啊！

于是我们多选择几个p 分别取一遍mod 只有一个值对所有的p取模之后全都0才算作解

哈希大法好！Hash Killer III至今无人AC就是在证明这个算法的正确性！哈希万岁！哈希赛高！哈希万年推！

时间复杂度O(nΣp+m) 其中Σp是选择的所有质数之和一般选择1W左右的质数就行了

不知道为什么不管考场上拿了多少分只要回来把题切了就算做精神AC了0.0……

#include
#include
#include
#include
#define M 110
using namespace std;
typedef long long ll;
const int prime[]={10007,11261,14843,19997,21893};
int n,m,stack[1001001],top;
ll a[M][5],f[21893][5];
inline ll F(int x,int j)
{
    int i;
    ll re=0;
    for(i=n;~i;i--)
        re=(re*x+a[i][j])%prime[j];
    return re;
}
inline void Input(int x)
{
    static char s[10100];
    int i,j;
    bool flag=false;
    scanf("%s",s+1);
    for(i=1;s[i];i++)
    {
        if(s[i]=='-')
            flag=true;
        else
            for(j=0;j<5;j++)
                a[x][j]=( (a[x][j]<<1) + (a[x][j]<<3) + s[i]-'0' )%prime[j];
    }
    if(flag) 
        for(j=0;j<5;j++)
            a[x][j]=prime[j]-a[x][j];
}
int main()
{
    int i,j;
    cin>>n>>m;
    for(i=0;i<=n;i++)
        Input(i);
     
    for(j=0;j<5;j++)
        for(i=0;i<prime[j];i++)
            f[i][j]=F(i,j);
         
    for(i=1;i<=m;i++)
    {
        for(j=0;j<5;j++)
            if(f[i%prime[j]][j])
                break;
        if(j==5)
            stack[++top]=i;
    }
     
    cout<<top<<endl;
    for(i=1;i<=top;i++)
        printf("%d\n",stack[i]);
}

内容总结

以上是互联网集市为您收集整理的NOIP2014D2T3解方程Hash大法好全部内容，希望文章能够帮你解决NOIP2014D2T3解方程Hash大法好所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/528651.html

来源：【匿名】

【上一篇】11gR2中的SCAN监听器和本地监听器配置【下一篇】用IE远程创建Mysql数据库的简易程序

更多 ►

【NOIP2014D2T3解方程Hash大法好】教程文章相关的互联网学习教程文章

Mysql 自定义HASH索引带来的巨大性能提升----[真相篇]【图】

推倒重来俗话说no zuo no die why you try,这时候我又忍不住zuo了，吭哧吭哧的把解决过程发上博客，向全世界宣布，哥又搞定个难题。剧情的发展往往是看起来主角完全掌握了局势的情况下，会突然跳出来一个很牛的反面人物，然后搞得主角很惨，搞的过程中主角开始小宇宙爆发，然后逆袭。这次也不例外。踢场子的人该出现了一顿狂侃之后，发现我原来牛逼的分析，完全经不起推敲。几个问题1）在未做HASH索引之前，为什么大表的ROWS那么...

MySQL hash分区（四）【图】

详细描述总结请看MySQL分区（一）例子：该例子为本人个人学习总结分享->详细说明-->有问题欢迎前来交流原文：http://blog.csdn.net/leyangjun/article/details/38233571

InnoDB的关键特性-插入缓存,两次写,自适应hash索引详解【图】

InnoDB存储引擎的关键特性包括插入缓冲、两次写（double write）、自适应哈希索引（adaptive hash index）。这些特性为InnoDB存储引擎带来了更好的性能和更高的可靠性。插入缓冲插入缓冲是InnoDB存储引擎关键特性中最令人激动的。不过，这个名字可能会让人认为插入缓冲是缓冲池中的一个部分。其实不然，InnoDB缓冲池中有Insert Buffer信息固然不错，但是Insert Buffer和数据页一样，也是物理页的一个组成部分。主键是行唯一的标...

Redis数据类型之HASH类型

Redis hash 是一个 string 类型的 field 和 value 的映射表.它的添加、删除操作都是 O(1) （平均）。 hash 特别适合用于存储对 HASH类型-特点 Redis hash 是一个 string 类型的 field 和 value 的映射表.它的添加、删除操作都是 O(1) （平均）。 hash 特别适合用于存储对象。相较于将对象的每个字段存成单个 string 类型。将一个对象存储在 hash 类型中会占用更少的内存，并且可以更方便的存取整个对象。省内存的原因是新建一...

MySQL的btree索引和hash索引的区别

ash 索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引。可能很多人又有疑问了，既然 Hash 索引的效率要比 B-Tree 高很多，为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢？任何事物都是有两面性的，Hash 索引也一样，虽然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也带来...

mysql之Innodb特性adaptive hash index【代码】

If a table fits almost entirely in main memory, the fastest way to perform queries on it is to use hash indexes. InnoDB has a mechanism that monitors index searches made to the indexes defined for a table. If InnoDB notices that queries could benefit from building a hash index, it does so automatically. The hash index is always built based on an existing B-tree index on the table. InnoDB can build...

MySQL索引类型 btree索引和hash索引的区别

Hash 索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引。可能很多人又有疑问了，既然 Hash 索引的效率要比 B-Tree 高很多，为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢？任何事物都是有两面性的，Hash 索引也一样，虽然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也带来...

MySQL-Comparison of B-Tree and Hash Indexes

PRIMARY KEY, UNIQUE, INDEX, and FULLTEXT) are stored in B-trees. Exceptions: Indexes on spatial data types use R-trees; MEMORY tables also support hash indexes; InnoDBuses inverted lists for FULLTEXT indexes. 没多少内容，直接看原文吧 http://dev.mysql.com/doc/refman/5.7/en/index-btree-hash.html 、只要使用了Limit mysql 会尽力使用索引、 MySQL-Comparison of B-Tree and Hash Indexes标签：本文系统来...

MySQL的btree索引和hash索引的区别【图】

。可能很多人又有疑问了，既然 Hash 索引的效率要比 B-Tree 高很多，为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢？任何事物都是有两面性的，Hash 索引也一样，虽然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端，主要有以下这些。（1）Hash 索引仅仅能满足"=","IN"和"<=>"查询，不能使用范围查询。由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值，所以它只能用于等值的过滤，不能用于基...

MySQL的btree索引和hash索引&聚集索引【图】

这样就可以理解为什么innodb的主键索引不能用离散的数据。下图为2层btree结构： 2，哈希索引建立在哈希表的基础上，它对每个值采用精确查找。每一行都需要先计算哈希码，比较好的哈希算法算出比较低的重复的度，这样效率相对高一些。如果算出来的值是一样的，那么它需要再进行判断哪个值才是想要的值，所以说在表里面采用哈希索引，但是重复度又比较高，那么哈希索引效率就比较低。 HASH索引PK BTREE索引：大量不同数据等值...

MySQL hash分区（四）【图】

具体描写叙述总结请看MySQL分区（一）样例：该样例为本人个人学习总结分享->具体说明-->有问题欢迎前来交流MySQL hash分区（四）标签：water ack 技术分享 img net data .net ext hash 本文系统来源：http://www.cnblogs.com/liguangsunls/p/7222194.html

nginx+PHP+memcached+MySQL+ip-hash做memcached集群【代码】

1、nginx与memcached整合#安装memcached支持的事务库libeventwget https://github.com/libevent/libevent/releases/download/release-2.0.22-stable/libevent-2.0.22-stable.tar.gz tar zxf libevent-2.0.22-stable.tar.gz cd libevent-2.0.22-stable ./configure --prefix=/usr/local/libevent make && make install echo $? cd ..#接下来安装memcached:wget http://www.memcached.org/files/memcached-1.4.35.tar.gz tar zxf me...

MySQL Hash索引和B-Tree索引的区别

MySQL Hash索引和B-Tree索引的区别究竟在哪里呢？相信很多人都有这样的疑问，下文对两者的区别进行了详细的分析，供您参考。 MySQL Hash索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引。可能很多人又有疑问了，既然 Hash 索引的效率要比 B-Tree 高很多，为什么大家不都用 Hash 索引而...

MySQL-如何删除hash表分区【代码】

一个大表，之前是以hash分区表的形式存在的，MySQL> show create table history_uint;| history_uint | CREATE TABLE `history_uint` ( `itemid` bigint(20) unsigned NOT NULL, `clock` int(11) NOT NULL DEFAULT ‘0‘, `value` bigint(20) unsigned NOT NULL DEFAULT ‘0‘, `ns` int(11) NOT NULL DEFAULT ‘0‘, PRIMARY KEY (`itemid`,`clock`,`ns`), KEY `i_clock` (`clock`) ) ENGINE=InnoDB DEFAULT CHARSET=utf8 /*!5010...

MySQL的btree索引和hash索引的区别

MySQL的btree索引和hash索引的区别ash 索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引。可能很多人又有疑问了，既然 Hash 索引的效率要比 B-Tree 高很多，为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢？任何事物都是有两面性的，Hash 索引也一样，虽然 Hash 索引效率高，但是...

MYSQL - 技术教程分类

MySQL 教程 MySQL 安装 MySQL 管理 MySQL PHP 语法 MySQL 连接 MySQL 创建数据库 MySQL 删除数据库 MySQL 选择数据库 MySQL 数据类型 MySQL 创建数据表 MySQL 删除数据表 MySQL 插入数据 MySQL 查询数据 MySQL WHERE 子句 MySQL UPDATE 更新 MySQL DELETE 语句 MySQL LIKE 子句 MySQL UNION MySQL 排序 MySQL 分组 MySQL 连接的使用 MySQL NULL 值处理 MySQL 事务 MySQL ALTER命令 MySQL 索引 MySQL 临时表 MySQL 复制表 MySQL 元数据 MySQL 序列使用 MySQL 处理重复数据 MySQL 及 SQL 注入 MySQL 导出数据 MySQL 导入数据 MySQL 函数 MySQL 运算符 mysql 全部

MYSQL - 最热教程

sql分组取最大记录方法 mysql如何设置默认值 mysql创建数据表时指定默认值教程 MySQL 5.7 的初始化操作（root初始密码...Oracle中合并数据集(多行变一行)mysql 相同内容的字段合并为一条的方法解决mysql设置时区时的错误Unknown or ...解决ubuntu下mysql的'Access denied fo...ubuntu系统中MysqlERROR1045(28000)报错...mysql数据库设置不区分大小写

首页 / MYSQL / NOIP2014D2T3解方程Hash大法好

NOIP2014D2T3解方程Hash大法好

内容导读

内容图文

内容总结

内容备注

内容手机端

【NOIP2014D2T3解方程Hash大法好】教程文章相关的互联网学习教程文章

MYSQL - 技术教程分类

MYSQL - 最新教程

MYSQL - 最热教程