[ 2018 Multi-University Training Contest 2 ] [ HDU6309 ] Absolute

题目大意：给定n个区间\([l_i , r_i]\)，\(-10^6 \leq l_i \leq r_i \leq 10^6\)且\(l_i , r_i\)都为整数，\(x_i\)为对应范围内的一个随机实数，求\(| \sum{x_i} | \)的期望。\( n \leq 15\)，答案对998244353取模。

题解：和http://zarxdy34.is-programmer.com/categories/63253/posts 基本上是一样的，容斥方法一样。

分成\(\sum{x_i}\)小于0和大于0两部分来考虑，两部分的做法一样。以小于0的部分为例，首先将范围进行调整，将\(x_i\)的范围调整为\([0,r_i - l_i]\)，那么符合条件的范围即\( \sum{l_i} + \sum{x_i} < 0\)，即\( 0 \leq |\sum{x_i}| < |\sum{l_i}| \)，求此时\( |\sum{l_i}| - |\sum{x_i}|\)的期望。容斥的方法和上面的那个是一样的，不同之处在于这题求的不是概率，还要考虑\(\sum{x_i}\)的期望。这里可以通过积分求出，当\[0 \leq x_i \leq a\] \[0 \leq \sum{x_i} \leq a\]时，该部分\(a - \sum{x_i}\)的期望为\(\frac{a^n}{xpro \cdot n!}\)，其中\(xpro = \prod{(r_i - l_i)}\)。（不是很严谨，意会一下即可）

#include <bits/stdc++.h>
using namespace std;
const int mo=998244353;

long long Pow(int x,int p)
{
	long long res=1,xx=x;
	while (p)
	{
		if (p&1) (res*=xx)%=mo;
		(xx*=xx)%=mo;
		p>>=1;
	}
	return res;
}

long long inv(int x){return Pow(x,mo-2);}
 
long long invp[17];
int l[15],r[15];
int x[15],xpro;
int n,lsum,rsum;

int DFS(int o,int sum,int dsum,int p)
{
	if (sum<=0) return 0;
	int res=0;
    if (o==n)
	{
		res=(Pow(sum,n+1)*invp[n+1]%mo*p+mo)%mo;
		return res;
	}
    res+=DFS(o+1,sum,dsum,p);
    res+=DFS(o+1,sum-x[o],dsum+x[o],-p);
    return res%mo;
}
 
int main()
{
	scanf("%d",&n);
	invp[0]=1;
	for (int i=1;i<=n+1;i++) invp[i]=invp[i-1]*inv(i)%mo;
	xpro=1;
	for (int i=0;i<n;i++)
	{
		scanf("%d%d",&l[i],&r[i]);
		if (x[i]) xpro=(long long)xpro*x[i]%mo;
		lsum+=l[i];
		rsum+=r[i];
	}
	if (lsum>=0 || rsum<=0)
	{
		printf("%lld\n",(long long)abs(lsum+rsum)*inv(2)%mo);
		return 0;
	}
	printf("%lld\n",((DFS(0,-lsum,0,1)*inv(xpro)%mo+mo)%mo+(DFS(0,rsum,0,1)*inv(xpro)%mo+mo)%mo)%mo);
    return 0;
}