Modulo Query ZOJ - 3940 (区间取模)_七九河开的博客-程序员秘密

技术标签: 数论  

题目

https://cn.vjudge.net/problem/ZOJ-3940

题意

给你n个模数,和一个0-m范围,Q次询问,每次问范围内有多少数结果是给定的数

思路

区间取模,对x个区间取模,最多会产生x+1个区间,即x个0-(x-1)的区间合并为一个,和0-(<x)的区间

所有最后最多会有2*n个区间,

对于所有的查询x,查找有多少区间又端点大于等于x,即答案

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9+7;
struct node
{
    int r,cnt;
    bool operator < (const node &a) const
    {
        return r < a.r;
    }
}a[500005];
int sum[500005];
int qw[500005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        node u;
        u.r = m,u.cnt = 1;
        priority_queue<node> q;
        q.push(u);
        for(int i = 1;i <= n;i++)
        {
            int x;
            scanf("%d",&x);
            while(q.top().r >= x)
            {
                u = q.top();
                q.pop();
                int cnt = u.cnt;
                while(!q.empty()&&q.top().r == u.r)
                {
                    cnt+=q.top().cnt;
                    q.pop();
                }
                node v;
                v.r = x - 1;
                int num = cnt*(u.r/x);
                v.cnt = num;
                q.push(v);
                v.r = u.r % x;
                v.cnt = cnt;
                q.push(v);
            }
        }
        int p = 0;
        while(!q.empty())
        {
            a[p].r = q.top().r;
            a[p++].cnt = q.top().cnt;
            q.pop();
        }
        sort(a,a+p);
        memset(sum,0,sizeof(sum));
        for(int i =p-1;i >= 0;i--)
        {
            sum[i] = sum[i+1] + a[i].cnt;
            qw[i] = a[i].r;
        }
        int Q;
        scanf("%d",&Q);
        ll ans = 0;
        for(int k = 1;k <= Q;k++)
        {
            int x;
            scanf("%d",&x);
            int id = lower_bound(qw,qw+p,x) - qw;
            ans += (ll)k*sum[id];
            ans %= mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/sdut_jk17_zhangming/article/details/89192309

智能推荐

GCC字符集设置_code&debug的博客-程序员秘密

原文:http://www.cnblogs.com/findumars/p/5624858.htmlGCC提供了以下的参数开关来支持其它文字编码的源文件: a)-finput-charset=charset gcc在默认情况下,总是假设源代码的编码是UTF-8,如果是其它编码的源代码文件,源代码里面又用到了wchar_t的类型,则可...

《C语言及程序设计》实践参考——长方形的周长和面积_c语言长方形周长和面积编程_迂者-贺利坚的博客-程序员秘密

返回:贺老师课程教学链接  C语言及程序设计初步  项目要求题目:编程序,输入长方形的两边长a和b,输出长方形的周长和面积提示:边长可以是整数也可以是小数;实现乘法的运算符是*参考解答:

作者:不详 文章来源:http://www.javathinker.org/bbs/topic.jsp?db=1_dingdangxiaoma的博客-程序员秘密

作者:不详 文章来源:http://www.javathinker.org/bbs/topic.jsp?db=15&amp;topic=3348 上传日期:2007-03-03 1.更新服务器 对于将MySQL安装为服务的,先使用net stop MySQL,如果没有将MySQL安装为服务,先停止服务,而后安装新的服务器软件。2.连接服务器shell&gt; my...

1/t的傅里叶变换证明_SilentLittleCat的博客-程序员秘密

-i*pi*sgn(ω);看到很多人只给了结论,这里简单说一下证明思路:其中有一些符号变换注意一下就可以了

编写程序,用一个 for 循环计算1+3+5+7 + ……+99的值,并输出计算结果。_php1+3+5+7+9+…+99_小刚博客的博客-程序员秘密

<div style="language:zh-CN;line-height:150%;margin-top:12.0pt;margin-bottom:0pt;margin-left:0in;text-indent:0in;text-align:justify;text-justify:inter-ideograph;direction:ltr;unicode-bidi:embed;mso-l

动态规划 - The Levenshtein Distance 编辑距离_天涯古巷的博客-程序员秘密

(一)问题样例给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作:• 插入一个字符• 删除一个字符• 替换一个字符【示例】输入:word1 = "benyam", word2 = "ephrem"输出:5(二)求解步骤1、确定状态- 找出最后一步- 化成子问题- 画出动态规划表 - 表的最后一格表示原问题, - 表的任意一格表示一个子问题- 填写动态规划表

随便推点

视频海报/同时添加水印文字效率问题实现的几种思路(比android微商管家效率快!)..._情迁666的博客-程序员秘密

第一种方法视频转换为图片 然后缩放到指定大小并裁剪然后图片每一帧与水印进行合并绘制, 文字进行合并绘制成一张新图然后提取音频文件然后合并处理后的每一张视频帧图并且和 音频进行合并第二种方法单独使用ffmpeg给视频进行缩放到指定比例 单独给图片缩放到指定比例,但是这里是视频要放到图片的下面,那么添加水印的方法 一般是水印比图片大,这里挖空透明的是 图片,如果图片转换为一个图片视频,那...

HTTP Status 404 / tomcat 404问题解决_Gordon_run的博客-程序员秘密

原文地址:HTTP Status 404 / tomcat 404问题解决https://blog.csdn.net/Tomwildboar/article/details/79662265  今天初次使用tomcat的时候,用浏览器访问总是不成功。经过一番周折总算成功了,虽然这个知识点不是很难,但还是写篇博客,希望能帮助那些初学者。(注:笔者用的是:tomcat 7)前提:你的tom...

vue中data为什么要写return返回值的问题_Frank杰的博客-程序员秘密

为什么要写return返回?因为不使用return包裹的数据会在项目的全局可见,会造成变量污染使用return包裹后数据中变量只在当前组件中生效,不会影响其他组件。这里记录一下,还有两种data的写法附在下面,提醒自己不要忘记。简单的vue实例data属性展现的形式:let app= newVue({ el:"#app", data:{ msg:'' }})使用组件化项目的形式:export default{ data(){ r

Linux 里的 2>&1 究竟是什么_挖坑埋你的博客-程序员秘密

我们在Linux下经常会碰到nohup command&amp;gt;/dev/null 2&amp;gt;&amp;amp;1 &amp;amp;这样形式的命令。首先我们把这条命令大概分解下:首先就是一个nohup:表示当前用户和系统的会话下的进程忽略响应HUP消息。&amp;amp;是把该命令以后台的job的形式运行。command&amp;gt;/dev/null较好理解,/dev/null表示一个空设备,就是说把 comman...

oracle创建唯一索引_徒步@天涯的博客-程序员秘密

create unique index idx_test_uid on test_uid(name) online tablespace tablespace2;附:1、作为一个好习惯,不要把索引和表格的数据放在同一个表空间。一般索引单独建一个表空间。2、建立索引切记加online这个参数,尤其是在大表操作。这个参数加上以后,除了create过程中index 保持online状态,Or...

推荐文章

热门文章

相关标签