出题人题解|完美皮肤

【ZSROI R1-D 完美皮肤】

前言：为了方便描述，在本题目里面的 $A_i,B_i$ 在本篇题解内会转为小写 $a_i,b_i$。

$30pts:$

$n\le 19$，可以猜出大概是一个 $O(2^nn)$ 的算法。

定义 $f_S$ 表示待选择集合为 $S$ 时还需要的天数期望。

有边界 $f_{\emptyset}=0$（即空集）

考虑转移 $f_S$，记 $A=\sum_{i\in S} a_i$，$B=\sum_{i\in S} b_i$，有：

$$f_S=\frac{A-B}{A} \times (f_S+1) +\sum_k \frac{b_k}{A}\times (f_{S \setminus \{k\}}+1)$$

解释一下：有 $\frac{A-B}{A}$ 的概率没有选到目标，有 $\frac{b_k}{A}$ 的概率选到 $k$ 的目标。

继续转移：

$$f_S=\frac{A-B}{A} \times f_S + \frac{A-B}{A} + \frac{B}{A} + \sum_k \frac{b_k}{A}\times f_{S \setminus \{k\}}$$

$$\frac{B}{A} f_S=1+\sum_k \frac{b_k}{A}\times f_{S \setminus \{k\}}$$

$$f_S=\frac{A}{B}+\sum_k \frac{b_k}{B} \times f_{S \setminus \{k\}}$$

解毕，转移即可。

#include <bits/stdc++.h>			
using namespace std;			
const int N = 19,S = 1<<N,mod = 1e9+7;			
int n,a[N],b[N],f[S];			
inline void add(int& x,int y){			
    x+=y;			
    if (x>=mod) x-=mod;			
}			
inline void mul(int& x,int y){			
    x = 1ll*x*y%mod;			
}			
inline int ksm(int exp,int p){			
    int ans = 1;			
    for(;p;p >>= 1,mul(exp,exp)){			
        if (p & 1) mul(ans,exp);			
    }			
    return ans;			
}			
int main(){			
    cin>>n;			
	for(int i = 0;i<n;++i){		
        cin>>a[i]>>b[i];			
    }			
	for(int s = 1;s<1<<n;++s){		
		int sp = 0,sm = 0;	
		for(int i = 0;i<n;++i) if(s>>i&1) add(sm,a[i]);	
		sm = ksm(sm,mod-2),f[s] = 1;	
		for(int i = 0;i<n;++i){	
            if(s>>i&1){			
    			int pr = 1ll*b[i]*sm%mod;
    			add(f[s],1ll*pr*f[s^1<<i]%mod),add(sp,pr);
            }			
		}	
        mul(f[s],ksm(sp,mod-2));			
	}		
    printf("%d",f[(1<<n)-1]);			
}			

时间复杂度：$O(2^NN)$

$100pts:$

结论：$f_S=\sum_{i\in S} \frac{a_i}{b_i}$

证明：首先该结论对于边界 $f_{\emptyset}$ 成立。

用归纳法，令 $t=\sum_{i\in{S}}\frac{a_i}{b_i}$，有 $f_{S \setminus \{k\}}=t-\frac{a_k}{b_k}$，推得：

$$f_S=\frac{A}{B}+\sum_k\frac{b_k}{B}\times f_{S \setminus \{k\}} =\frac{A}{B}+\sum_k\frac{b_k}{B}\times(t-\frac{a_k}{b_k})=t$$

归纳完成，答案为 $\sum_{i=1}^n \frac{a_i}{b_i}$

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
#define ll long long
ll ksm(ll x,ll exp){
    x%=mod;
    ll ans = 1;
    while(exp){
        if(exp&1) ans = ans*x%mod;
        x = x*x%mod;
        exp>>=1;
    }
    return ans;
}
void make(ll &fz,ll &fm,ll fz2,ll fm2){
    ll nfm = fm*fm2%mod;
    ll nfz = (fz*fm2%mod+fz2*fm%mod)%mod;
    fz = nfz;
    fm = nfm;
}
int main() {
    ll fm,fz,a,b,n;
    cin>>n>>a>>b;
    fz = a%mod;
    fm = b%mod;
    for(int i = 1;i<n;++i){
        ll fz2,fm2;
        cin>>fz2>>fm2;
        make(fz,fm,fz2%mod,fm2%mod);
    }
    cout<<fz*ksm(fm,mod-2)%mod;
}		

时间复杂度：$O(N)$