NOIP2023模拟13联测34 competition

题目大意

给定一个有$n$个选手的团队去参加比赛，比赛有$m$道题，每个选手可以$100\%$将第$l_i\sim r_i$道题做出来。

比赛时，团队会随机派出编号连续的人去做题，得分为做出来题目的总数。

求该团队参加比赛的期望得分。

答案对$1e9+7$取模。

题目思路

我们先考虑暴力做法，先$n^2$枚举派出那些选手去参加比赛，然后$\log n$算出他们一共能做出多少道题，最后答案就是所有可能做出来的题目数量乘上$\frac{n\ast (n+1)}{2}$在模意义下的逆元即可。

现在考虑正解。

我们可以将枚举区间改为计算每道题对答案的贡献。

设$ls{t}_j$记录的是$i$前面第一个可以做出来$j$的人。

一开始假设每道题都会被包含在任意区间，然后顺序枚举$i$，对于$l_i\sim r_i$中的每个$j$，我们设$ls{t}_j$表示$i$前面第一个可以做出这道题的人，因为$(ls{t}_j,i)$中的区间不包含$j$，所以$j$不会对这个区间中的任意区间做贡献，答案就应该减去$\frac{(i-ls{t}_j)\ast (i-ls{t}_j-1)}{2}$。

考虑怎么维护$ls{t}_j$，一开始$ls{t}_j$全为$0$，每次操作后都会将$lst$数组中$l_i\sim r_i$赋值为$i$，所以$lst$可以用柯朵莉树维护。

最后在乘上方案数的逆元即可。

具体实现参考代码。

#include
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'&&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()&&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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84