沧州企业网站制作的,网站开发中安全性的防范,网站关键词多少个合适,2008 访问网站提示建设中正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId1667 题目大意
两个人。 第一个人有k1k_1k1个集合#xff0c;第iii个包括了范围[L1i,R1i][L1_i,R1_i][L1i,R1i]的整数。 第二个人有k2k_2k2个集合#xff0c;第iii个包括了范围[L2i,R2i][L2_i…正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId1667 题目大意
两个人。 第一个人有k1k_1k1个集合第iii个包括了范围[L1i,R1i][L1_i,R1_i][L1i,R1i]的整数。 第二个人有k2k_2k2个集合第iii个包括了范围[L2i,R2i][L2_i,R2_i][L2i,R2i]的整数。
现在两个人分别从各个集合中取出一个数字然后求和。
求第一个人大于/等于/小于第二个人的概率。
1≤T≤5,≤k1,k2≤8,1≤L,R≤1071\leq T\leq 5,\leq k_1,k_2\leq 8,1\leq L,R\leq 10^71≤T≤5,≤k1,k2≤8,1≤L,R≤107 解题思路
很神奇的题设xi∈[0,R1i−L1i],yi∈[0,R2i−L2i]x_i\in[0,R1_i-L1_i],y_i\in[0,R2_i-L2_i]xi∈[0,R1i−L1i],yi∈[0,R2i−L2i]那么要求求小于的话 ∑i1k1L1i∑i1k1xi∑i1k2R2i−∑i1k2yi\sum_{i1}^{k_1}L1_i\sum_{i1}^{k_1}x_i\sum_{i1}^{k_2}R2_i-\sum_{i1}^{k_2}y_ii1∑k1L1ii1∑k1xii1∑k2R2i−i1∑k2yi ⇒∑i1k1xi∑i1k2yi∑i1k2R2i−∑i1k1L1i\Rightarrow \sum_{i1}^{k_1}x_i\sum_{i1}^{k_2}y_i\sum_{i1}^{k_2}R2_i-\sum_{i1}^{k_1}L1_i⇒i1∑k1xii1∑k2yii1∑k2R2i−i1∑k1L1i 右边是已知的那考虑到kkk很小那这个问题就是一个很简单的组合数问题了。
枚举一些突破范围限制的数然后容斥即可。
时间复杂度O(2kk)O(2^kk)O(2kk) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll P1e97;
ll T,n,m,sum,S,ans1,ans2,ans3,w[30],inv[30];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
ll C(ll n,ll m){ll ans1;for(ll in;in-m;i--)ansans*i%P;return ans*inv[m]%P;
}
void dfs(ll x,ll s,ll f,ll sum){if(s0)return;if(xnm){(sumC(snm,nm)*f)%P;return;}dfs(x1,s,f,sum);dfs(x1,s-w[x]-1,-f,sum);return;
}
signed main()
{inv[1]1;for(ll i2;i30;i)inv[i]P-inv[P%i]*(P/i)%P;inv[0]1;for(ll i1;i30;i)inv[i]inv[i-1]*inv[i]%P;scanf(%lld,T);while(T--){scanf(%lld,n);sum-1;S1;for(ll i1,l;in;i)scanf(%lld%lld,l,w[i]),w[i]w[i]-l,sum-l,SS*(w[i]1)%P;scanf(%lld,m);for(ll in1,l;inm;i)scanf(%lld%lld,w[i],l),w[i]l-w[i],suml,SS*(w[i]1)%P;ll ans10;dfs(1,sum,1,ans1);ll ans20;dfs(1,sum1,1,ans2);ll ans3(S-ans2)%P,invnpower(S,P-2);ans2(ans2-ans1)%P;ans3ans3*invn%P;ans1ans1*invn%P;ans2ans2*invn%P;printf(%lld %lld %lld\n,(ans3P)%P,(ans2P)%P,(ans1P)%P);}return 0;
}
