题面在

题意

开始时袋中有\(t\)种小球,第\(i\)种小球有\(t_i\)个,之后每次等概率取出一个球,第\(i\)次取球时观察这个球的颜色\(c_i\)放回并向袋中加入\(d\)个颜色为\(c_i\)的球;

给出一组询问\([x_i,y_i](1\le i\le n)\),求同时满足第\(x_i\)次取球的颜色为\(y_i\)的概率

\(1≤t,n≤1000, 1≤a_k ,d≤10, 1≤x_1<x_2<…<x_n≤10000, 1≤y_k≤t\)

hint

有没有注意到\(1≤x_1<x_2<…<x_n≤10000\)这个条件?

感觉又鬼畜又没有用对么?

~~那么我们把这个条件删掉~~

其实这个条件仅仅是在给你一个提示

sol

其实我做题的时候也不知道这个条件有什么用...~~于是我就没有做出来~~

如果\(x_i=i\)你还不会做?直接模拟即可

所以这道题直接模拟就可以了。

！！！！！！~~是的很震惊对吧~~

给你\(1≤x_1<x_2<…<x_n≤10000\)这个条件,

就是让你考虑怎么把这个条件化成\(x_i=i\)的......

接下来我们开始证明,

如果仅仅考虑一次抽取的情况,每次抽到颜色\(c\)的概率都是一样的,

即第\(i\)次抽到颜色\(c\)的概率和第\(i+1\)次抽到颜色\(c\)的概率相同

设第\(i\)次抽之前,袋子里总共有\(tot\)个球,有\(a\)个颜色为\(c\)的球(update 4.4:感谢 @GuessYCB的更正 orz)

那么第\(i\)次抽抽到\(c\)的概率显然是\(P_i=\frac{a}{tot}\)

那么第\(i+1\)次抽抽到\(c\)的概率呢?

\[P_{i+1}=\frac{a}{tot}\times\frac{a+d}{tot+d}+(1-\frac{a}{tot})\times\frac{a}{tot+d}=\frac{a}{tot}=P_i\]

嗯是的

于是直接把\([x_1,x_2,x_3,...,x_n]\)转换为\([1,2,3,...,n]\)即可

注意高精(可以考虑先\(fact\),最后再化系数)

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  #include
                   
                    #define mp make_pair#define pb push_back#define RG register#define il inlineusing namespace std;typedef unsigned long long ull;typedef vector
                    
                     VI;typedef long long ll;typedef double dd;const dd eps=1e-10;const int mod=1e9+7;const int N=5010;const int M=20010;il ll read(){ RG ll data=0,w=1;RG char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')w=-1,ch=getchar(); while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar(); return data*w;}il void file(){ //freopen("a.in","r",stdin); //freopen("a.out","w",stdout);}int t,n,d,a[N],y[N],sum;int pri[M],vis[M];il void sieve(){ vis[1]=1; for(RG int i=2;i
                     
                      =10)s[i+1]+=s[i]/10,s[i]%=10; while(s[ws+1])ws++,s[ws+1]+=s[ws]/10,s[ws]%=10; } il void print(){ for(RG int i=ws;i;i--)printf("%d",s[i]); }}A[3];il void solve(){ for(RG int i=1,minn;i<=pri[0];i++){ minn=min(sys[1][i],sys[2][i]); sys[1][i]-=minn;sys[2][i]-=minn; } A[1].init();A[2].init(); for(RG int id=1;id<=2;id++) for(RG int i=1;i<=pri[0];i++) for(RG int j=1;j<=sys[id][i];j++)A[id].times(pri[i]); A[2].print();printf("/");A[1].print();puts("");}int main(){ t=read();n=read();d=read();sieve(); for(RG int i=1;i<=t;i++)a[i]=read(),sum+=a[i]; for(RG int i=1;i<=n;i++) read(),y[i]=read(),fact(a[y[i]],2),a[y[i]]+=d,fact(sum,1),sum+=d; solve();return 0;}