城口网站建设,网站建设中下载,wordpress评论显示ua,首页图片点击率如何提高题目大意
有一场题目数量为 m m m的比赛#xff0c;有一个团队想要来参加。
这个团队有 n n n个选手#xff0c;编号为 i i i的选手能做第 l i ∼ r i l_i \sim r_i li∼ri道题#xff0c;每题他都有 100 % 100\% 100%的概率做出来。
这个团队会随机派出一只队伍来参…题目大意
有一场题目数量为 m m m的比赛有一个团队想要来参加。
这个团队有 n n n个选手编号为 i i i的选手能做第 l i ∼ r i l_i \sim r_i li∼ri道题每题他都有 100 % 100\% 100%的概率做出来。
这个团队会随机派出一只队伍来参加这个比赛。
因为编号相邻的人关系更好默契度也更高所以一个团队派出的队伍一直都是编号为连续区间的选手。
一个队伍的得分为该队伍能做出的题的数量求这个团队参加比赛的期望得分。输出答案模 1 0 9 7 10^97 1097后的值。
注 一道题只能被做出来一次。 1 ≤ n ≤ 1 0 6 , 1 ≤ l i ≤ r i ≤ m ≤ 1 0 18 1\leq n\leq 10^6,1\leq l_i\leq r_i\leq m\leq 10^{18} 1≤n≤106,1≤li≤ri≤m≤1018
时间限制 2000 m s 2000ms 2000ms空间限制 512 M B 512MB 512MB。 题解
直接求能做出多少道题并不简单我们换一种思路对于每道题有多少种队伍做不出这道题
对于每道题 k k k我们设 z i z_i zi表示 k k k是否包含在 [ l i , r i ] [l_i,r_i] [li,ri]中也就是第 i i i个人能不能做出这道题。那么如果当前的队伍不能做出这道题那选择的区间就不能包含任意一个 z i 1 z_i1 zi1的 i i i。也就是说将所有 z i 1 z_i1 zi1的 i i i放在一起则相邻的两个数 i , j i,j i,j之间有 t j − i − 1 tj-i-1 tj−i−1个人不会做这道题那么这部分中有 t ( t 1 ) 2 \dfrac{t(t1)}{2} 2t(t1)种队伍的选法使得这道题不能被做出来。
我们先求每种方案的得分之和那么可以先将每种方案的得分都先看作 m m m然后再减去不能做出的题目。
对于每道题 k k k维护在 i i i之前最后一个能做出这道题的人 l s t k lst_k lstk。然后遍历每个人遍历 l i l_i li到 r i r_i ri每个位置 k k k的贡献为 t ( t 1 ) 2 \dfrac{t(t1)}{2} 2t(t1)其中 t i − l s t k − 1 ti-lst_k-1 ti−lstk−1然后令 l s t k i lst_ki lstki。这样做的话时间复杂度为 O ( n m ) O(nm) O(nm)。下面考虑优化。
我们用一个 v e c t o r vector vector来存储 l s t lst lst值相同的每一个区间一开始总共只有一个区间 [ 1 , m ] [1,m] [1,m] l s t lst lst值都是 0 0 0。对于每个人 i i i都要修改 [ l i , r i ] [l_i,r_i] [li,ri]上的 l s t lst lst值。那么我们对于 v e c t o r vector vector中每一个与 [ l i , r i ] [l_i,r_i] [li,ri]有交集的区间 [ a , b ] [a,b] [a,b]将这些区间与 [ l i , r i ] [l_i,r_i] [li,ri]有交集的部分按上面的方法向答案做出 t ( t 1 ) 2 × ( b − a 1 ) \dfrac{t(t1)}{2}\times (b-a1) 2t(t1)×(b−a1)的贡献注意这里的贡献是负的是在原本将这道题看作做对然后在减去不能做对的方案数乘上题目数量因为这个区间表示 m m m道题中的 b − a 1 b-a1 b−a1道题所以要乘上 ( b − a 1 ) (b-a1) (b−a1)。再把有交集部分删掉没有交集的部分再放回去。最后加上一个区间 [ l i , r i ] [l_i,r_i] [li,ri] l s t lst lst值为 i i i。因为最后还有一部分没有算贡献的我们可以在最后再加入一个区间 [ 1 , m ] [1,m] [1,m] l s t lst lst值为 n 1 n1 n1就能够统计到这部分的贡献。
这样做的话会不会 TLE \text{TLE} TLE呢不会。因为每次加入一个区间最多能够产生 3 3 3个区间这个区间本身与这个区间有交集的区间中最左边的没有交集的部分与这个区间有交集的区间中最右边的没有交集的部分为保证区间是从小到大排序的所以加入一次区间的时间复杂度为 O ( log n ) O(\log n) O(logn)区间总数不会超过 3 n 3n 3n。而每个区间在之后如果与新加入的区间有交集则这个区间就会被删去也就是说在之后最多只造成 O ( 1 ) O(1) O(1)的时间复杂度。所以总时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)。
我们最终得到了每种方案的得分之和再乘上方案数的逆元即可。
时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)。
code
#includebits/stdc.h
using namespace std;
const int N1000000;
const long long mod1e97;
int n;
long long m,ans0;
struct node{long long x,y,w;bool operator(const node ax)const{return yax.y;}
};
vectornodev;
long long mi(long long t,long long v){if(!v) return 1;long long remi(t,v/2);rere*re%mod;if(v1) rere*t%mod;return re;
}
long long gt(long long k){return k*(k1)/2%mod;
}
void pt(long long x,long long y,long long w){auto itlower_bound(v.begin(),v.end(),(node){0,x,0});node vl(node){0,0,-1},vr(node){0,0,-1};while((*it).xy){if((*it).xx) vl(node){(*it).x,x-1,(*it).w};if((*it).yy) vr(node){y1,(*it).y,(*it).w};long long vxmax(x,(*it).x),vymin(y,(*it).y);ans(ans-(vy-vx1)%mod*gt(w-(*it).w-1)%modmod)%mod;v.erase(it);}int vtit-v.begin();if(vr.w!-1) v.insert(v.begin()vt,vr);v.insert(v.begin()vt,(node){x,y,w});if(vl.w!-1) v.insert(v.begin()vt,vl);
}
int main()
{
// freopen(competition.in,r,stdin);
// freopen(competition.out,w,stdout);scanf(%d%lld,n,m);ansm%mod*gt(n)%mod;v.push_back((node){1,m,0});v.push_back((node){m1,m1,0});for(int i1;in;i){long long x,y;scanf(%lld%lld,x,y);pt(x,y,i);}pt(1,m,n1);ansans*mi(gt(n),mod-2)%mod;printf(%lld,ans);return 0;
}
