频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
[NOI2006] 神奇口袋 - nosta - 博客园
2019-05-25 20:02:58         来源:nosta バカ  
收藏   我要投稿

[NOI2006] 神奇口袋

之前遇到的题完全无印象,倒是本地有一份题解,略作修改放上来。

[NOI2006]神奇口袋

题目

一个口袋中先放有\(a_i\;(1\le a_i,\;1\le i\le t)\)个\(i\)颜色的球。若在第\(i\)次从中取到的球色为\(C_i\),则要向口袋中放入\(d\)个与之同色的求,取到的球也要放回。每个球被取到的几率相同。

先给出\(Q=\{(x_n,y_n)\}\),询问全部满足在第\(x_i\)次取球时取到颜色\(y_i\)的几率。

分析

结论

假设当前\(Q\)中的\(x\)有序。

结论一: \(Q\)中\(x\)离散后对结果无影响

证明:

设在第\(k\)次取球时,颜色\(c\)的数目为\(a[c]\),球的总数为\(tot\)。可以得出:

在第\(k\)次取到\(c\)的几率为\(P_k=\dfrac{a[c]}{tot}\) 。又因为

在第\(k\)次取到\(c\)且在第\(k+1\)次也取到的几率为\(P_1=\dfrac{a[c]}{tot}\times\dfrac{a[c]+d}{tot+d}\)。 在第\(k\)次没取到\(c\),但在第\(k+1\)取到的几率为\(P_2=\dfrac{tot-a[c]}{tot}\times\dfrac{a[c]}{tot+d}\)。

故在第\(k+1\)次取到\(c\)的几率为\(P_{k+1}=P_1+P_2=\dfrac{(tot+d)\times a[c]}{(tot+d)tot}=\dfrac{a[c]}{tot}\)。

即\(P_k=P_{k+1}\)。再经过简单归纳,即可证明结论一成立。

结论二: \(Q\)中\(y\)的出现顺序对结果无影响

证明:

设在第\(i\)次取球时,颜色\(c\)的数目为\(a[c]\),球的总数为\(tot\)。对于\(y_i,y_{i+1}(1\le i 若\(y_i=y_{i+1}\),显然无影响 若\(y_i\not=y_{i+1}\),则 交换之前两组\((x,y)\)都成立的几率为\(P_1=\dfrac{a[y_i]}{tot}\times\dfrac{a[y_{i+1}]}{tot+d}\)。 交换之后两组\((x,y)\)都成立的几率为\(P_2=\dfrac{a[y_{i+1}]}{tot}\times\dfrac{a[y_i]}{tot+d}\)。

发现\(P_1=P_2\),即此时也无影响。同样的,略作归纳可知本结论成立。

算法

由以上两个结论的得出\(x\)的顺序无影响,\(y\)的循序也无影响。故可以直接在读入\(Q\)时对\(y\)依次处理即可。

注意此题需要用到高精度、GCD。为了方便处理,可以对分子分母进行分解。最终将两个数的各个因子合起来。

实例
#include 
using namespace std;
const int N=1010;
const int P=200000;
struct BigInt {
    int s[P],ws;
    BigInt(){s[1]=1;ws=1;}
    void Multi(int x) {
        for(int i=1;i<=ws;++i)s[i]=s[i]*x;
        for(int i=1;i<=ws;++i)s[i+1]+=s[i]/10,s[i]%=10;
        while(s[ws+1])++ws,s[ws+1]=s[ws]/10,s[ws]%=10;
    }
    void output(){for(int i=ws;i;--i) printf("%d",s[i]);}
}U,D;
int t,n,d,tot,a[N];
int cntp,pri[P],num[P];
bool notp[P]={1,1};
void addon(int x,int w) {
    for(int i=1; x&&i<=cntp; ++i) {
        while(x%pri[i]==0) num[i]+=w, x/=pri[i];
    }
}
int main() {
    for(int i=2; i0; --num[i]) U.Multi(pri[i]);
        for(; num[i]<0; ++num[i]) D.Multi(pri[i]);
    }
    U.output();
    putchar('/');
    D.output();
    return 0;
}

点击复制链接 与好友分享!回本站首页
相关TAG标签 - - 博客园
上一篇:C# 身份证号码15位和18位验证 - 梵音2019 - 博客园
下一篇:Windows服务使用Windsor容器 - repeatedly - 博客园
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站