なるほど…。
https://yukicoder.me/problems/no/2876
問題
N人の人がおり、1人目はウイルスに感染している。
ウイルスに感染した人は、1回そのウイルスをばらまく。そうすると、未感染の人はそれぞれ確率xで感染する。
N,xが与えられたとき、ウイルスに感染する人数の期待値を求めよ。
解法
N点の無向グラフを考える。
2点間に確率xで辺を張るとき、頂点1を含む連結成分のサイズの期待値が、問題の解と同じとなる。
あとは上記値をDPで求めることを考える。
C(n) := 頂点nのグラフが連結である確率
S(n,k) := 頂点nのグラフのうち、頂点1を含む連結成分のサイズがkとなる確率
C(n) = S(n,n) = 1-(S(n,1)+S(n,2)+...S(n,n-1)) となる。
S(n,k)は、あるk頂点が連結で、他の(n-k)点と辺を持たない確率なので、S(n,k) = Comb(n-1,k-1)*C(k)*(1-x^(k*(n-k)))
nの小さい順に上記値を求めて行けばよい。
int N,X;
const ll mo=998244353;
ll P[2525*2525];
ll C[2525];
ll S[2525][2525];
ll modpow(ll a, ll n = mo-2) {
ll r=1;a%=mo;
while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
return r;
}
ll comb(ll N_, ll C_) {
const int NUM_=400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
if (fact[0]==0) {
inv[1]=fact[0]=factr[0]=1;
for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
}
if(C_<0 || C_>N_) return 0;
return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}
void solve() {
int i,j,k,l,r,x,y; string s;
cin>>N>>X;
X=X*modpow(100)%mo;
P[0]=1;
FOR(i,N*N) P[i+1]=P[i]*(1+mo-X)%mo;
C[1]=1;
S[1][1]=1;
for(int n=2;n<=N;n++) {
C[n]=1;
for(i=1;i<=n;i++) {
S[n][i]=comb(n-1,i-1)*C[i]%mo*P[i*(n-i)]%mo;
if(i!=n) (C[n]+=mo-S[n][i])%=mo;
}
}
ll ret=0;
for(k=1;k<=N;k++) (ret+=k*S[N][k])%=mo;
cout<
まとめ
うまく問題を言い換えるのが難しいな…。
