【2018QBXT刷题游记】

Day5 TEST8

T2 schedule

【问题描述】

共有 n 件事情，编号为 1, 2, …, n，第 i 件事情的难度为 i. 划分为 m 个时刻，并设定了三个正整数 a, b, c。

定义一个数列{xi}，满足：

x0=0,xi=(a∗xI−1+b)mod  2∗n∗c(1≤i≤m)x_{0} = 0, x_{i} = (a*x_{I−1}+ b) \mod 2*n*c (1 ≤ i ≤ m)x0​=0,xi​=(a∗xI−1​+b)mod2∗n∗c(1≤i≤m)

即从 x_{1} 开始，数列的每项等于上一项的 a 倍加上 b 以后除以 2nc 的余数。

开始时日程表是空的. 第 i 个时刻前，

1. 若 xi < nc，则将编号为⌊xc⌋+1⌊\frac{x}{c}⌋ + 1⌊cx​⌋+1的事件加⼊日程表，若日程表已有该事件则忽略；
2. 若 xi ≥ nc，则将编号为 ⌊xc⌋−n+1⌊\frac{x}{c}⌋ - n+ 1⌊cx​⌋−n+1 的事件从日程表删除，若日程表没有该事件则忽略；
   第 i 个时刻（1 ≤ i ≤ m），所做的事情就是该时刻日程表中的所有事件.
   对于每个时刻，定义该时刻的g工作量为该时刻做了几件事情，该时刻的疲劳度为该时刻做的所有事情的难度之和.

根据 n, m, a, b, c 计算总工作量和疲劳度.

n≤5×107，m≤2×106，a≤106，b≤109，c≤5×104n ≤ 5×10^7，m ≤ 2×10^6，a ≤ 10^6，b ≤ 10^9，c ≤ 5×10^4n≤5×107，m≤2×106，a≤106，b≤109，c≤5×104

【分析】一道模拟题，不过这n有点大啊……

于是我欢快地开大了数组。爆零快乐！

其实只需要判断一下当前时刻加入或删除的数就可以啦，用t1和t2表示在计划表里的工作量和疲劳度即可~

#include
    
     #include
     
      #include
      
       using namespace std;#define ll long long#define MAXN 2000005bool vis[50000005];ll n,m,a,b,c,t1,t2;#define MOD 1000000007ll gzl,pld;int main(){	freopen("schedule.in","r",stdin);	freopen("schedule.ans","w",stdout); 	scanf("%lld%lld%lld%lld%lld",&n,&m,&a,&b,&c);	ll tmp=0;ll qaq=n*c;	for(ll i=1;i<=m;i++){		tmp=(a*tmp+b)%(qaq*2);		if(tmp
       
        0){			ll noww=tmp/c-n+1;			if(vis[noww]){			vis[noww]=0;			t1=(t1-1+MOD)%MOD;			t2=(t2-noww+MOD)%MOD;}		}}		gzl=(gzl+t1)%MOD;		pld=(pld+t2)%MOD;	}	printf("%lld %lld\n",gzl,pld);	return 0;}