The main idea of the title
Given a
n
n
A team of n players goes to participate in the competition. The competition has
m
m
m questions, each player can
100
%
100\%
100% will be
l
i
~
r
i
l_i \sim r_i
li?~ri? Questions are completed.
During the competition, the team will randomly send people with consecutive numbers to do the questions, and the score will be the total number of questions completed.
Find the expected score for the team participating in the game.
The answer is right
1
e
9
+
7
1e9+7
1e9 + 7 modulo.
Question ideas
Let’s consider violence first, first
n
2
n^2
n2 enumeration sends those players to participate in the competition, and then
log
?
n
\log n
logn calculates how many questions they can do in total. The final answer is the number of all possible questions multiplied by
n
?
(
n
+
1
)
2
\frac{n*(n + 1)}{2}
The inverse element of 2n?(n + 1)? in the modular sense is sufficient.
Now consider the correct answer.
We can change the enumeration interval to calculate the contribution of each question to the answer.
set up
l
s
t
j
lst_j
What lstj? records is
i
i
The first one in front of i can be made
j
j
j person.
At the beginning, it is assumed that each question will be included in any interval, and then enumerated sequentially
i
i
i, for
l
i
~
r
i
l_i \sim r_i
each of li?～ri?
j
j
j, we assume
l
s
t
j
lst_j
lstj? means
i
i
The first person in front of i who can solve this question, because
(
l
s
t
j
,
i
)
(lst_j,i)
The interval in (lstj?,i) does not contain
j
j
j, so
j
j
j will not contribute to any interval within this interval, the answer should be subtracted
(
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?lstj1)?.
Consider how to maintain
l
s
t
j
lst_j
lstj?, at first
l
s
t
j
lst_j
lstj?all for
0
0
0, will be changed after each operation
l
s
t
lst
in lst array
l
i
~
r
i
l_i \sim r_i
li?~ri? are assigned values of
i
i
i, so
l
s
t
lst
lst can be maintained with Kodoli trees.
Finally, multiply it by the inverse element of the plan number.
Specific implementation reference code.
#include<bits/stdc + + .h>
using namespace std;
long long n,m,ans=0;
const long long mod=1e9 + 7,inv=5e8 + 4;
struct node
{<!-- -->
long long l,r;
mutable long long v;
node(long long L,long long R=-1,long long V=0)
{<!-- -->
l=L,r=R,v=V;
}
bool operator<(const node &a) const
{<!-- -->
return l<a.l;
}
};
set<node> a;
long long read()
{<!-- -->
long long s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{<!-- -->
if(ch=='-')
w=-1;
ch=getchar();
}
while(ch>='0' & amp; & amp;ch<='9')
s=s*10 + (ch-'0'),ch=getchar();
return s*w;
}
auto split(long long pos)
{<!-- -->
auto it=a.lower_bound(pos);
if(it!=a.end() & amp; & amp;it->l==pos)
return it;
it--;
long long l=it->l;
long long r=it->r;
long long v=it->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 itr=split(r + 1);
auto itl=split(l);
for(auto it=itl;it!=itr; + + it)
ans=(ans-(it->r-it->l + 1)*(k-it->v)%mod*(k-it->v-1)%mod*inv%mod + mod)% mod;
a.erase(itl,itr);
a.insert(node(l,r,k));
return ;
}
long long ksm(long long a,long long b)
{<!-- -->
long long sum=1;
while(b)
{<!-- -->
if(b&1)
sum=sum*a%mod;
a=a*a%mod;
b>>=1;
}
return sum;
}
int main()
{<!-- -->
freopen("competition.in","r",stdin);
freopen("competition.out","w",stdout);
n=read(),m=read();
a.insert(node(1,m + 10,0));
ans=m%mod*n%mod*(n + 1)%mod*inv%mod;
for(int i=1;i<=n; + + i)
{<!-- -->
long long l=read(),r=read();
emerge(l,r,i);
}
emerge(1,m,n + 1);
ans=ans*ksm(n*(n + 1)%mod*inv%mod,mod-2)%mod;
printf("%lld",ans);
return 0;
}