河南建设网站公司哪家好,网站建设邀请函,装修公司加盟哪家好,天津网站建设制作方案题目大意
给定一个有 n n n个选手的团队去参加比赛#xff0c;比赛有 m m m道题#xff0c;每个选手可以 100 % 100\% 100%将第 l i ∼ r i l_i \sim r_i li∼ri道题做出来。
比赛时#xff0c;团队会随机派出编号连续的人去做题#xff0c;得分为做出来题目的总数。…题目大意
给定一个有 n n n个选手的团队去参加比赛比赛有 m m m道题每个选手可以 100 % 100\% 100%将第 l i ∼ r i l_i \sim r_i li∼ri道题做出来。
比赛时团队会随机派出编号连续的人去做题得分为做出来题目的总数。
求该团队参加比赛的期望得分。
答案对 1 e 9 7 1e97 1e97取模。
题目思路
我们先考虑暴力做法先 n 2 n^2 n2枚举派出那些选手去参加比赛然后 log n \log n logn算出他们一共能做出多少道题最后答案就是所有可能做出来的题目数量乘上 n ∗ ( n 1 ) 2 \frac{n*(n1)}{2} 2n∗(n1)在模意义下的逆元即可。
现在考虑正解。
我们可以将枚举区间改为计算每道题对答案的贡献。
一开始假设每道题都会被包含在任意区间然后顺序枚举 i i i对于 l i ∼ r i l_i \sim r_i li∼ri中的每个 j j j因为 ( l s t j , i ) (lst_j,i) (lstj,i)中的区间不包含 j j j所以 j j j不会对这个区间中的任意区间做贡献答案就应该减去 ( i − l s t j ) ∗ ( i − l s t j − 1 ) 2 \frac{(i-lst_j)*(i-lst_j-1)}{2} 2(i−lstj)∗(i−lstj−1)。
考虑怎么维护 l s t j lst_j lstj一开始 l s t j lst_j lstj全为 0 0 0每次操作后都会将 l s t lst lst数组中 l i ∼ r i l_i \sim r_i li∼ri赋值为 i i i所以 l s t lst lst可以用柯朵莉树维护。
最后在乘上方案数的逆元即可。
具体实现参考代码。
#includebits/stdc.h
using namespace std;
long long n,m,ans0;
const long long mod1e97,inv5e84;
struct node
{long long l,r;mutable long long v;node(long long L,long long R-1,long long V0){lL,rR,vV;}bool operator(const node a) const{return la.l;}
};
setnode a;
long long read()
{long long s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9)ss*10(ch-0),chgetchar();return s*w;
}
auto split(long long pos)
{auto ita.lower_bound(pos);if(it!a.end()it-lpos)return it;it--;long long lit-l;long long rit-r;long long vit-v;a.erase(it);a.insert(node(l,pos-1,v));return a.insert(node(pos,r,v)).first;
}
void emerge(long long l,long long r,long long k)
{auto itrsplit(r1);auto itlsplit(l);for(auto ititl;it!itr;it)ans(ans-(it-r-it-l1)*(k-it-v)%mod*(k-it-v-1)%mod*inv%modmod)%mod;a.erase(itl,itr);a.insert(node(l,r,k));return ;
}
long long ksm(long long a,long long b)
{long long sum1;while(b){if(b1)sumsum*a%mod;aa*a%mod;b1;}return sum;
}
int main()
{freopen(competition.in,r,stdin);freopen(competition.out,w,stdout);nread(),mread();a.insert(node(1,m10,0));ansm%mod*n%mod*(n1)%mod*inv%mod;for(int i1;in;i){long long lread(),rread();emerge(l,r,i);}emerge(1,m,n1);ansans*ksm(n*(n1)%mod*inv%mod,mod-2)%mod;printf(%lld,ans);return 0;
}
