[洛谷P3600]随机数生成器

栏目: 编程工具 · 发布时间: 5年前

我真是傻逼,这道题做了两个晚上还没做出来,巫蛊偶大佬看了一眼就秒掉了,后来还是在巫蛊偶神仙的提示下做出来的……只能说明我太菜了。

首先我们可以发现如果一段区间包含了另外一段区间,那么大的区间是没有用的。所以我们去掉所有没有用的区间之后把这些区间按左端点 排序 之后右端点一定也是单调递增的。这些区间大概可能是张这样的:

[洛谷P3600]随机数生成器

然后因为期望不能做极值问题所以我们肯定是要枚举这个最小值的最大值的。

我们发现形如答案是某个值的方案数非常难求,所以我们可以把它变为形如答案小于等于某个值的方案数,最后处理一下就好了。然后考虑使用DP来解。

首先枚举这个值k,一个很显然的DP是$f(i,j)$表示到第i个位置,正好前面j个区间的最小值已经小于等于k的方案数,这是一个2d/0d动态规划,我们改变一下状态就可以把他变为一个1d/1d动态规划。$f(i)$表示正好前i段区间的区间最小值已经小于等于k的方案数,然后预处理一下逆元,用一些数学式子转移一下就好了。然后我们发现这个貌似可以用一个类似于前缀和的东西优化,所以就没了,时间复杂度$O(n^2)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=2005,MOD=666623333;
int fpow(int x,int n){
    int ret=1;
    for(;n;n>>=1,x=(ll)x*x%MOD)
        n&1?ret=(ll)ret*x%MOD:0;
    return ret;
}
int f[MAX_N][MAX_N],c[MAX_N],b[MAX_N],p[MAX_N][MAX_N],inv[MAX_N][MAX_N];
pair<int,int> a[MAX_N];
int main(){
    int n,x,q; scanf("%d%d%d",&n,&x,&q);
    for(int i=1;i<=q;++i) scanf("%d%d",&a[i].first,&a[i].second);
    for(int i=1;i<=q;++i)
        for(int j=1;j<=q;++j)
            if(i!=j&&a[j].first!=-1&&a[i].first<=a[j].first
                &&a[i].second>=a[j].second){
                a[i].first=-1;
                break;
            }
    int top=0;
    for(int i=1;i<=q;++i)
        if(a[i].first!=-1) a[++top]=a[i];
    sort(a+1,a+top+1);
    q=top;
    for(int i=1;i<=x;++i){
        p[i][0]=1,p[i][1]=(ll)i*fpow(x,MOD-2)%MOD;
        inv[i][0]=1,inv[i][1]=fpow(p[i][1],MOD-2);
        for(int j=2;j<=n+2;++j){
            p[i][j]=(ll)p[i][j-1]*p[i][1]%MOD;
            inv[i][j]=(ll)inv[i][j-1]*inv[i][1]%MOD;
        }
    }
    for(int i=1;i<=q;++i) b[a[i].first]++,c[a[i].second+1]++;
    for(int t=1;t<x;++t){
        f[t][0]=1;
        int poi=0,cnt=0,key=0;
        for(int i=1;i<=n;++i){
            if(b[i]){
                key=((ll)f[t][poi]*p[x-t][n-a[poi+1].first]+key)%MOD;
                ++cnt,++poi;
            }
            if(c[i]){
                key=(key+MOD-(ll)f[t][poi-cnt]
                    *p[x-t][n-a[poi-cnt+1].first]%MOD)%MOD;
                --cnt;
            }
            f[t][poi]=(f[t][poi]+(ll)key*inv[x-t][n-i]%MOD*p[t][1])%MOD;
        }
    }
    f[x][q]=1;
    int ans=0;
    for(int i=1;i<=x;++i){
        ans=((ll)i*(f[i][q]+MOD-f[i-1][q])+ans)%MOD;
    }
    printf("%d",ans);
    return 0;
}
 

以上所述就是小编给大家介绍的《[洛谷P3600]随机数生成器》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

C程序设计的抽象思维

C程序设计的抽象思维

Eric S.Roberts / 闪四清 / 机械工业出版社 / 2012-5 / 99.00元

Eric S. Roberts所著的《C程序设计的抽象思维》是一本关于C语言的经典图书。本书共计17章,分为4部分,第一部分概述计算机导论课程中涉及的基本编程概念;第二部分讨论递归算法,其中结合大量示例,有助于读者轻松理解和掌握晦涩的概念;第三部分不仅介绍了用非递归算法实现的抽象数据类型,还提供了一些工具,有助于读者理解数据抽象的概念;第四部分重点介绍采用递归算法实现的抽象数据类型。本书重点突出,......一起来看看 《C程序设计的抽象思维》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器