时间限制：2 秒 / 内存限制：1024 MiB

L K N
A1​ A2​ … AN​

5 2 2
0 1

4

3 1 1
2

1

5 2 5
0 1 2 3 4

80

7 3 3
0 2 3

12

思路

设一个端点的两个线段不交叉。

考虑任意黑色区域。

当该区域包含一段弧时，我们为该弧的每个端点分配权重 1/2 。当该区域不包含弧时，该区域有一个唯一且距离圆心最远的顶点。我们为该点分配权重 1 。

关注一个端点，它两边必有一黑色区域，而它有1/2的概率使用，所以，它的的权重的期望是1/4。

关注两条任意弦的交点，首先，选中两条弦的概率为1/4，如果没有任何其他弦将圆心与这个交点隔开，概率为0，它的的权重的期望是0，否则，权重为 1 的概率为 1/2，它的的权重的期望是1/8。

若有x个交点，y为满足 i 的ai+k<=a[i+1]的数量。这里我们设a[n+i]=a[i]+l 。

没有其他弦将它们与圆心分开的交点数是n-y。

所以，总的期望值为

n/2+x/8-n/8+y/8。

代码见下

#include<bits/stdc++.h>
using namespace std;
long long l,k,n,a[550005],b[250005],s[250005],mod=998244353,lk=0;
long long pow2(long long a1,long long b1,long long m1){
    long long kk1=1;
    while(b1>=1){
        if(b1%2==1){
            kk1*=a1;
        }
        b1/=2;
        a1*=a1;
        kk1%=m1;
        a1%=m1;
    }
    return kk1;
}
int main(){
	cin>>l>>k>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i+n]=a[i]+l;
		b[i]=a[i]+k;
	}
	for(int i=1;i<=n;i++){
		long long l=1,r=2*n,md=2*n;
		while(l<=r){
			long long mid=(l+r)/2;
			if(a[mid]>=a[i]+k){
				md=min(md,mid);
				r=mid-1;
			}
			else{
				l=mid+1;
			}
		}
		md-=i;
		//cout<<md<<endl;
		s[md]++;
	}	
	for(int i=2;i<=n;i++){
		lk=(lk+((i-1)*((s[i]*pow2(2,n-3,mod))%mod))%mod)%mod;
	}
	lk=(lk+(s[1]*pow2(2,n-3,mod))%mod)%mod;
	lk=(lk+n*pow2(2,n-1,mod))%mod;
	lk=((lk-n*pow2(2,n-3,mod))%mod+mod)%mod;
	//lk=(lk+n*pow2(2,n-3,mod)*3)%mod;
	//lk=(lk+s[0]*pow2(2,n-3,mod)*3)%mod;
	cout<<lk<<endl;
	return 0;
}