preface

Cloud shear plate link

cnblogs I believe you! So I launched all the blog topic solving chains!

Deleted or modified

あウー... Please indicate the source for reprint

Probability expectation notes

In order to save space, the code is compressed Mivik's code press ), you can format it yourself if you want to see it

Default source: header file (\ (14,15 \) question default Gauss elimination)

Mapping table

Upd. S. There are no more t questions (chemistry, draw cards). There are only \ (18 \) questions left

1. The fate of mung bean frog

Problem surface

link

Random walk on a weighted DAG with \ (n \) points, ask the edge weight and expectation of the path from \ (1 \) to \ (n \)

Brief explanation

For a simple question, let \ (dp_ \) be the version edge and expectation from \ (1 \) to \ (n \), which is defined by expectation

Where \ (\ deg u \) is the penetration of \ (U \)

The transfer order is an inverted topological order

code

using namespace std;const int N=1e5+500;typedef long long ll;typedef double db;int n,m,deg[N],ii[N];bool vis[N];db dp[N];vector<pair<int,int>>g[N];inline void addedge(int u,int v,int w){g[u].emplace_back(make_pair(v,w));++deg[v];++ii[v];}void koishi(int s){queue<int>q;q.push(s);dp[s]=0;while(!q.empty()){int u=q.front();q.pop();for(auto e:g[u]){int v=e.first,w=e.second;dp[v]+=(dp[u]+w)/deg[v];if(!--ii[v])q.push(v);}}}int main(){scanf("%d%d",&n,&m);for(int i=0,u,v,w;i<m;i++)scanf("%d%d%d",&u,&v,&w),addedge(v,u,w);koishi(n);printf("%.2f",dp[1]);return 0;}

2. Congcong and cocoa

Problem surface

link

An undirected graph with \ (n \) points \ (m \) edges. Two cute \ (A,B \) walk on the graph. The initial \ (A \) is at point \ (m \), \ (B \) is at point \ (c \). The walking method of \ (A,B \) at each time is as follows:

• \(A \) walk randomly on the graph (\ (A \) may not move)
• \The strategy of (B \) is to select the exit point closest to \ (A \) at A time, and take another step if it does not reach \ (A \)

Each time \ (A \) goes first and \ (B \) then. Ask how many times you expect to meet \ (A,B \)

Brief explanation

The second question is poison tumor, sobbing

Firstly, the maze of \ (B \) can be preprocessed: let \ (to(i,j) \) indicate where \ (B \) should go when \ (B \) is \ (i \) and \ (A \) is \ (j \)

Let \ (dp_{i,j} \) represent the number of schemes in which \ (B \) is in \ (I \) and \ (A \) is in \ (j \), then

• If \ (i=j \), then \ (dp_{i,j}=0 \)
• If \ (I \) takes \ (1,2 \) steps to \ (A \), then \ (dp_{i,j}=1 \)
• If not, then:

Where \ (tr (I, K) = to (I, K), i.e. \ (I \) takes two steps

Run dp according to the equation, done!

code

using namespace std;const int N=1145;typedef long long ll;typedef double db;int n,m,s,t,dis[N][N],deg[N],to[N][N];db dp[N][N];bool vis[N],viss[N][N];vector<int>g[N];inline void addedge(int u,int v){g[u].emplace_back(v);++deg[u];}void bfs(int s){memset(vis,0,sizeof vis);queue<int>q;q.push(s);dis[s][s]=0;while(!q.empty()){int u=q.front();q.pop();if(vis[u])continue;vis[u]=true;for(auto v:g[u]){if(vis[v])continue;q.push(v);dis[s][v]=min(dis[s][v],dis[s][u]+1);}}}db dfs(int u,int v){if(viss[u][v])return dp[u][v];if(u==v)return 0;int t1=to[u][v],t2=to[t1][v];if((t1==v)||(t2==v))return 1;dp[u][v]=1;for(auto e:g[v])dp[u][v]+=dfs(t2,e)/(deg[v]+1);dp[u][v]+=dfs(t2,v)/(deg[v]+1);viss[u][v]=true;return dp[u][v];}int main(){memset(dis,0x3f,sizeof dis);memset(to,0x3f,sizeof to);scanf("%d%d%d%d",&n,&m,&s,&t);for(int i=0,u,v;i<m;i++)scanf("%d%d",&u,&v),addedge(u,v),addedge(v,u);for(int i=1;i<=n;i++)bfs(i);for(int i=1;i<=n;i++)for(auto v:g[i])for(int j=1;j<=n;j++)if(dis[i][j]-1==dis[v][j])to[i][j]=min(to[i][j],v);printf("%.3f",dfs(s,t));return 0;}

3. OSU!

Problem surface

link

A random 01 string. The probability that the \ (I \) character is \ (1 \) is \ (a_i \)

The expectation of finding the cubic sum of extremely long continuous \ (1 \) segments

Problem solution

Love to see osu!

\(\ mathbb E^k(x) \) represents the expectation of the length of extremely long continuous \ (1 \) segment to the power of \ (K \) and (the \ (x \) is \ (1 \))

Obviously \ (\ mathbb E^1(x)=(\mathbb E^1(x)+1)a_i \), so it can be linearly recursive

What's going on?

Why? Complete square formula

similar

The current condition is that the \ (x \) is \ (1 \). If you want to lose it, you only need to add a \ (\ mathbb E^3(x-1)(1-a_i) \) after it

Code space complexity \ (O(n) \), you can do \ (O(1) \) by rolling

code

using namespace std;const int N=100050;int n;double E1[N],E2[N],ans;int main(){scanf("%d",&n);double tmp;for(int i=1;i<=n;i++){scanf("%lf",&tmp);E1[i]=(E1[i-1]+1)*tmp;E2[i]=(E2[i-1]+2*E1[i-1]+1)*tmp;ans+=(3*E2[i-1]+3*E1[i-1]+1)*tmp;}printf("%.1f",ans);return 0;}

4. Red is good

Problem surface

link

There are \ (R \) \ (1 \) and \ (B \) \ (- 1 \), which are randomly disrupted, selected in turn, and can be stopped at any time

What is the expected sum of numbers under the optimal strategy

Problem solution

DP, if the answer is \ (dp_{R,B} \), then

Is it obvious

Why \ (\ max\{\cdots,0 \} \)? Because the best strategy - stop

You can roll, but I don't want to roll

code

using namespace std;const int N=5141;typedef long long ll;typedef double db;int r,b;db dp[N][N];int main(){scanf("%d%d",&r,&b);for(int i=1;i<=r;i++)dp[i][0]=i;for(int i=1;i<=r;i++)for(int j=1;j<=b;j++)dp[i][j]=max(0.0,1.0*j/(i+j)*(dp[i][j-1]-1)+1.0*i/(i+j)*(dp[i-1][j]+1));ll integer=floor(dp[r][b]),_=floor(dp[r][b]*1e6-integer*1e6);printf("%lld.%06lld",integer,_);return 0;}

5. The guardian's challenge

Problem surface

link

Problem solution

Let \ (dp_{i, j, k} \) represent the probability that the previous \ (I \) challenge won \ (j \) and the remaining capacity is \ (k \)

Isn't this a fucking number of \ (200\times 200\times 200000=8\times 10^9 \)?

The capacity \ (k \) is only useful if it is not greater than \ (n \), so the number of States is actually \ (8\times 10^6 \), which can be exceeded~

There are details

code

using namespace std;const int N=222;typedef long long ll;typedef double db;int n,l,k;struct thing{db p;int a;thing()=default;bool operator<(const thing&x){return a>x.a;}}a[N];db dp[N][N][N];int main(){scanf("%d%d%d",&n,&l,&k);for(int i=1;i<=n;i++)scanf("%lf",&a[i].p),a[i].p*=0.01;for(int i=1;i<=n;i++)scanf("%d",&a[i].a);sort(a+1,a+1+n);k=min(k,n);dp[0][0][k]=1;for(int i=1;i<=n;i++)for(int j=0;j<i;j++)for(int k=0;k<=n;k++){dp[i][j][k]+=dp[i-1][j][k]*(1-a[i].p);if(a[i].a+k>=0)dp[i][j+1][min(n,a[i].a+k)]+=dp[i-1][j][k]*a[i].p;}db ans=0;for(int j=l;j<=n;j++)for(int k=0;k<=n;k++)ans+=dp[n][j][k];printf("%.6f\n",ans);return 0;}

6. Easy

Problem surface

link

Uniform random 01 string, find the expected sum of extremely long continuous \ (1 \) segments

Problem solution

OSU! Weakened version

code

slightly

7. Single choice dislocation

Problem surface

link

Uniform random sequence, the value of bit \ (I \) is \ ([1, a_i]\cap \mathbb Z \)

Circularly rotate one bit and ask the expectation of equal number of corresponding bits in the sequence

Problem solution

Expected linearity, split into two adjacent bits with the same probability

In classical probability, the number of schemes is divided by the number of schemes. The answer in (I) is \ (\ dfrac {\ min \ {a_i, a_ {i+1} \} {a_ia_ {i+1} \), \ (i+1 \) needs rotation

code

using namespace std;const int N=1e7+500;int n,A,B,C,a[N];int main(){scanf("%d%d%d%d%d",&n,&A,&B,&C,a+1);for(int i=2;i<=n;i++)a[i]=((long long)a[i-1]*A+B)%100000001;for(int i=1;i<=n;i++)a[i]=a[i]%C+1;double ans=1.0/max(a[1],a[n]);for(int i=1;i<n;i++)ans+=1.0/max(a[i],a[i+1]);printf("%.3f",ans);return 0;}

8. Line up for spring outing

Problem surface

link

Problem solution

This problem pit, not even a sample
Well, I'm a good dish, QwQ

Lemma 1.

That is, the expectation of the value of \ (x \) is equal to the sum of the probabilities that it is greater than or equal to a certain number

Proof.
From the definition of expectation

The certificate is completed

Lemma 2

As we all know, \ (\ dbinom nm=\dbinom{n-1}m+\dbinom{n-1}{m-1} \)

Then, after substituting this formula to the following \ (\ dbinom{n-1}{m-1} \), you can get

The original formula \ (n-i+1 \) when \ (I \) takes \ (1\dots n \), it also takes \ (1\dots n \) so that

The certificate is completed

The expected linearity is still obvious

Calculate the expectation of each child's vision, which is defined by the expectation:

Mom, isn't this the form of Lemma 1? Put it on directly

Then \ (\ mathbb P(d\ge i) \) how to find

Suppose there are \ (k \) children whose height is not less than the child \ (i \) (this can be easily calculated), so they will block the child \ (i \) > <, Just arrange them

The classical concept, the ratio of the number of schemes, and the denominator are obviously put casually (which will block the children and themselves) \ (a {n} ^{K + 1} \)

Consider constraints:

• The person who will block the children cannot be in \ (i-1 \) positions in front of the children >_<
• The person who will block the children cannot be in the position of the children (grass)

This scheme is \ (a {n-i} ^ k \), and then the children have \ (n-i+1 \) positions to stand, so multiply by another \ (n-i+1 \)

To sum up, yes

Isn't it very simple

\(O(n^2) \) no, although the theory is too strong, the numerator and denominator are too large

Push a wave of formula. Anyway, every step is obvious

The penultimate equal sign is Lemma 2

So you ask hard once and it's over, \ (O(n) \)

code

using namespace std;typedef double db;const int M=1234;int n,b[M],k;db ans;int main(){scanf("%d",&n);for(int i=1,x;i<=n;i++)scanf("%d",&x),++b[x];for(int i=1;i<=1000;i++){ans+=1.0*b[i]*(n+1)/(n+1-k);k+=b[i];}printf("%.2f",ans);return 0;}

9. Rectangular painting

Problem surface

link

\(n\times m \) rectangle, brush one rectangle randomly at a time, and ask how many squares you expect to brush after \ (k \) times

Problem solution

The linearity of expectation can be imagined by everyone on earth

Then it becomes the probability of dyeing a point. The probability of dyeing once is \ (P \), and the probability of dyeing \ (K \) times is \ (1-(1-p)^k \)

Notice that there's a lot to talk about computing / tuu

code

using namespace std;const int N=1e5+500;typedef long long ll;typedef double db;int k,n,m;db ans=0;inline db sqr(const db&x){return x*x;}int main(){scanf("%d%d%d",&k,&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){db p=(sqr((i-1)*m)+sqr((j-1)*n)+sqr((n-i)*m)+sqr((m-j)*n)-sqr((i-1)*(j-1))-sqr((i-1)*(m-j))-sqr((n-i)*(j-1))-sqr((n-i)*(m-j)))/sqr(n*m);ans+=1-pow(p,k);}printf("%.0f",ans);return 0;}

10. Card game

Problem surface

link

Problem solution

The probability of each person winning is only related to his relative position with the dealer in the arrangement

Let \ (dp(i,j) \) be the probability of winning from the \ (j \) of the dealer when there are \ (i \) individuals left

Enumerate which card to choose this time

Where \ (t \) is the dead person, i.e. \ (t=(a_k-1)\bmod (i+1) \)

code

using namespace std;const int N=1e3+500;typedef long long ll;typedef double db;int k,n,m,a[N];db dp[N][N];int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d",a+i);dp[1][1]=1;for(int i=2;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=m;k++){int t=(a[k]-1)%i+1;if(t==j)continue;dp[i][j]+=dp[i-1][(j-t+i)%i]/m;}for(int i=1;i<=n;i++)printf("%.2f%% ",dp[n][i]*100);return 0;}

11. Change classrooms

Problem surface

link

Problem solution

slightly

code

slightly

12. Reward off

Problem surface

link

Problem solution

Big water problem, shape pressure dp

\(dp_{k, S} \) played \ (K \) times and selected \ (S \)

No

code

using namespace std;const int N=16,EN=(1<<N),K=111;typedef long long ll;typedef double db;int k,n,s[N],p[N];db dp[K][EN];int main(){scanf("%d%d",&k,&n);int _=(1<<n);for(int i=1;i<=n;i++){scanf("%d",p+i);int x;while(~scanf("%d",&x)&&x)s[i]|=(1<<(x-1));}for(int i=k;i>=1;i--)for(int j=0;j<_;j++)for(int k=1;k<=n;k++){db __=dp[i+1][j];if((j&s[k])==s[k])__=max(__,dp[i+1][j|(1<<(k-1))]+p[k]);dp[i][j]+=__/n;}printf("%.6f",dp[1][0]);return 0;}

13. Probability charger

Problem surface

[link]

Problem solution

Look at the question and guess it is to change the root, but I didn't think of it / qd
From the expected linearity, the answer is the probability of power on at each point

It's not easy to find this. Let's find out the probability of no power at each point

Analyze the contribution of each point:

1. Power on yourself
2. Power up in subtree
3. Power on outside subtree

Let \ (f(u) \) be the probability of self power on and power on in the subtree, then

Why? Because the contribution can be divided into:

• The subtree has no power
• The subtree has electricity, but there is no electricity

Let \ (g(u) \) represent the power on probability outside the subtree. We can consider what is outside the subtree of \ (u \):

• \(u \) outside the father's subtree
• \The subtree of the father of (u \) except the part of the subtree of \ (u \)

The first contribution is obvious

As for the second, because we are in the form of continuous product, it is over to directly eliminate the contribution of our son

Therefore, there is the probability of electricity outside the subtree of \ (u \):

Then a similar contribution:

• The subtree has no power
• The subtree has electricity, but there is no electricity

So there is

This dp from father to son can do dfs from top to bottom

Note that the special denominator is \ (0 \)

code

using namespace std;typedef long long ll;typedef double db;const int N=514114;vector<pair<int,db>>g[N];inline void addedge(int u,int v,db w){g[u].emplace_back(make_pair(v,w));}inline void ade(int u,int v,db w){addedge(u,v,w);addedge(v,u,w);}int n;db p[N],dp1[N],dp2[N];void dfs1(int u,int fa){dp1[u]=1-p[u];for(auto e:g[u]){int v=e.first;db w=e.second;if(v==fa)continue;dfs1(v,u);dp1[u]*=dp1[v]+(1-dp1[v])*(1-w);}}void dfs2(int u,int fa){for(auto e:g[u]){int v=e.first;db w=e.second;if(v==fa)continue;if(dp1[v]+(1-dp1[v])*(1-w)==0)continue;db P=dp2[u]*dp1[u]/(dp1[v]+(1-dp1[v])*(1-w));dp2[v]=P+(1-P)*(1-w);dfs2(v,u);}}int main(){scanf("%d",&n);db w;for(int i=1,u,v;i<n;i++)scanf("%d%d%lf",&u,&v,&w),ade(u,v,w/100);for(int i=1;i<=n;i++)scanf("%lf",p+i),p[i]/=100;dp2[1]=1;dfs1(1,0);dfs2(1,0);db ans=0;for(int i=1;i<=n;i++)ans+=1-dp1[i]*dp2[i];printf("%.6f\n",ans);return 0;}

14. Swimming

Problem surface

link

Problem solution

Consider counting the expected number of passes \ (dp_i \) at each point first, so

Because the starting point is \ (1 \), special judgment is required

The Gauss elimination is solved directly, and then the expected number of times of each edge \ ((u,v) \) is

Just sort them out

code

Card accuracy. I'll let \ (eps=10^{-10} \) pass here. Don't open long double

using namespace std;const int N=555,M=125678;const double eps=1e-10;int n,m,deg[N];double a[N][N],rk[M];vector<int>g[N];inline void addedge(int u,int v){g[u].emplace_back(v);++deg[v];}inline void ade(int u,int v){addedge(u,v);addedge(v,u);}struct Edge{int u,v;Edge(int _,int __):u(_),v(__){};Edge()=default;};vector<Edge>ed;void create(){a[1][n]=1;for(int u=1;u<n;u++){a[u][u]=1;for(auto v:g[u])if(v!=n)a[u][v]=-1.0/deg[v];}}/*Gauss elimination is expected here*/int main(){scanf("%d%d",&n,&m);for(int i=0,u,v;i<m;i++){scanf("%d%d",&u,&v);ade(u,v);ed.push_back(Edge(u,v));}create();Gauss(n-1);int l=ed.size();for(int i=0;i<l;i++){int u=ed[i].u,v=ed[i].v;if(u!=n)rk[i+1]+=a[u][n]/deg[u];if(v!=n)rk[i+1]+=a[v][n]/deg[v];}sort(rk+1,rk+1+m);double ans=0;for(int i=1;i<=m;i++)ans+=(m-i+1)*rk[i];printf("%.3f\n",ans);return 0;}

15. XOR and path

Problem surface

link

I'm interested in solving the problem. It's a cancer

Defined by expectations, contributions can be split

xor can be considered bit by bit, so we deal with each

Let \ (dp_ \) represent the probability that the path xor sum from \ (u \) to \ (n \) is \ (1 \), then

Gauss elimination is considered because it may have aftereffect

When you're done, pay attention to the influence of the heavy edge self ring

Time complexity \ (O(wn^3) \), where \ (w \) is the number of bits of edge weight

code

using namespace std;const int N=333;const double eps=1e-9;int n,m,deg[N];double a[N][N];vector<pair<int,int>>g[N];inline void addedge(int u,int v,int w){g[u].emplace_back(make_pair(v,w));++deg[v];}inline void ade(int u,int v,int w){addedge(u,v,w);addedge(v,u,w);}void create(int _){a[n][n]=1;for(int u=1;u<n;u++){a[u][u]=deg[u];for(auto e:g[u]){int v=e.first,w=e.second;if(w&(1<<_)){++a[u][v];++a[u][n+1];}else--a[u][v];}}}inline bool z(const double&x){return abs(x)<eps;}/**/int main(){scanf("%d%d",&n,&m);for(int i=0,u,v,w;i<m;i++){scanf("%d%d%d",&u,&v,&w);addedge(u,v,w);if(u!=v)addedge(v,u,w);}double ans=0;for(int i=0;i<32;i++){memset(a,0,sizeof a);create(i);Gauss();ans+=pow(2,i)*a[1][n+1];}printf("%.3f",ans);return 0;}

16. Breaking up is a wish

Problem surface

link

Problem solution

Stream of consciousness

Let \ (dp_i \) represent the expected number of operations from \ (I \) keys to be pressed to \ (i-1 \) keys to be pressed, so

code

using namespace std;const int N=100011,P=100003;typedef long long ll;int n,k,a[N],cc;ll dp[N];void init(){for(int i=n;i>=1;i--){if(!a[i])continue;++cc;for(int j=1;j*j<=i;j++)if(!(i%j)){a[j]^=1;if(j*j!=i)a[i/j]^=1;}}}ll qpow(ll a,ll n){ll ans=1;while(n){if(n&1)ans=ans*a%P;a=a*a%P;n>>=1;}return ans;}ll inv(int x){return qpow(x,P-2)%P;}int main(){scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%d",a+i);init();for(int i=n;i>=1;i--)dp[i]=(n+(n-i)*dp[i+1]%P)%P*inv(i)%P;ll ans;if(cc<=k)ans=cc;else{ans=k;for(int i=k+1;i<=cc;i++)ans=(ans+dp[i])%P;}for(int i=1;i<=n;i++)ans=ans*i%P;printf("%lld\n",ans);return 0;}

17, 18

No, it's rotten