当前位置： 移动技术网 > IT编程>开发语言>C/C++ > [NOI2006] 神奇口袋

[NOI2006] 神奇口袋

2019年05月26日  | 移动技术网IT编程  | 我要评论

贯通的近义词,翟鸿燊讲座,相公 造反吧

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

[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<n)\)，有

  • 若\(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 <bits/stdc++.h>
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; i<p; ++i) {
        if(!notp[i]) pri[++cntp]=i;
        for(int j=1; j<=cntp&&pri[j]*i<p; ++j) {
            notp[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
    scanf("%d%d%d",&t,&n,&d);
    for(int i=1; i<=t; ++i) {
        scanf("%d",&a[i]);
        tot+=a[i];
    }
    for(int i=1,x,y; i<=n; ++i) {
        scanf("%d%d",&x,&y);
        if(!a[y]) {puts("0/1"); return 0;}
        addon(a[y],1);
        addon(tot,-1);
        a[y]+=d, tot+=d;
    }
    for(int i=1; i<=cntp; ++i) {
        for(; num[i]>0; --num[i]) u.multi(pri[i]);
        for(; num[i]<0; ++num[i]) d.multi(pri[i]);
    }
    u.output();
    putchar('/');
    d.output();
    return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网