正题

题目链接:http://www.51nod.com/Challenge/Problem.html#problemId=1667

题目大意

两个人。

第一个人有\(k_1\)个集合，第\(i\)个包括了范围\([L1_i,R1_i]\)的整数。

第二个人有\(k_2\)个集合，第\(i\)个包括了范围\([L2_i,R2_i]\)的整数。

现在两个人分别从各个集合中取出一个数字然后求和。

求第一个人大于/等于/小于第二个人的概率。

\(1\leq T\leq 5,\leq k_1,k_2\leq 8,1\leq L,R\leq 10^7\)

解题思路

很神奇的题，设\(x_i\in[0,R1_i-L1_i],y_i\in[0,R2_i-L2_i]\)那么要求（求小于的话）

\[\sum_{i=1}^{k_1}L1_i+\sum_{i=1}^{k_1}x_i<\sum_{i=1}^{k_2}R2_i-\sum_{i=1}^{k_2}y_i
\]

\[\Rightarrow \sum_{i=1}^{k_1}x_i+\sum_{i=1}^{k_2}y_i<\sum_{i=1}^{k_2}R2_i-\sum_{i=1}^{k_1}L1_i
\]

右边是已知的，那考虑到\(k\)很小那这个问题就是一个很简单的组合数问题了。

枚举一些突破范围限制的数然后容斥即可。

时间复杂度：\(O(2^kk)\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const ll P=1e9+7;

ll T,n,m,sum,S,ans1,ans2,ans3,w[30],inv[30];

ll power(ll x,ll b){

	ll ans=1;

	while(b){

		if(b&1)ans=ans*x%P;

		x=x*x%P;b>>=1;

	}

	return ans;

}

ll C(ll n,ll m){

	ll ans=1;

	for(ll i=n;i>n-m;i--)ans=ans*i%P;

	return ans*inv[m]%P;

}

void dfs(ll x,ll s,ll f,ll &sum){

	if(s<0)return;

	if(x>n+m){

		(sum+=C(s+n+m,n+m)*f)%=P;

		return;

	}

	dfs(x+1,s,f,sum);

	dfs(x+1,s-w[x]-1,-f,sum);

	return;

}

signed main()

{

	inv[1]=1;for(ll i=2;i<30;i++)inv[i]=P-inv[P%i]*(P/i)%P;

	inv[0]=1;for(ll i=1;i<30;i++)inv[i]=inv[i-1]*inv[i]%P;

	scanf("%lld",&T);

	while(T--){

		scanf("%lld",&n);sum=-1;S=1;

		for(ll i=1,l;i<=n;i++)

			scanf("%lld%lld",&l,&w[i]),w[i]=w[i]-l,sum-=l,S=S*(w[i]+1)%P;

		scanf("%lld",&m);

		for(ll i=n+1,l;i<=n+m;i++)

			scanf("%lld%lld",&w[i],&l),w[i]=l-w[i],sum+=l,S=S*(w[i]+1)%P;

		ll ans1=0;dfs(1,sum,1,ans1);

		ll ans2=0;dfs(1,sum+1,1,ans2);

		ll ans3=(S-ans2)%P,invn=power(S,P-2);

		ans2=(ans2-ans1)%P;ans3=ans3*invn%P;

		ans1=ans1*invn%P;ans2=ans2*invn%P;

		printf("%lld %lld %lld\n",(ans3+P)%P,(ans2+P)%P,(ans1+P)%P);

	}

	return 0;

}

巴特西

51nod1667-概率好题【容斥,组合数学】

正题

题目大意

解题思路

code

最新文章

热门文章