【题解】世界杯

题意

给你个人的之间比赛的胜率，这之间进行单淘汰赛制，问编号为的人夺冠的概率是多少。

题解

首先单淘汰赛制和二进制的关系很密切。

设某一轮比赛为，求和两只队伍是否能比赛，下面我们用二进制来表示队伍的队号

0001(1)
0010(2)
0011(3)
0100(4)
0101(5)
0110(6)
0111(7)
1000(8)

我们让所有的队伍先减1
得到

0000(1)
0001(2)
0010(3)
0011(4)
0100(5)
0101(6)
0110(7)
0111(8)

对于第局比赛只能是相连的两支队伍进行比赛，我们观察一下发现，，，，他们除了最后一位，他们的前缀都是相同的，那么我们抹去最后的位，即进行右左移操作。对于左移完的结果，发现能够比赛的两个号码之间只有最后一位是不同的，我们可以通过异或操作来消除最后一位的差异。
对于第局比赛时，对于来说他可与比赛我们再抹去后位时，，与第一局的情况是类似的，能与进行比赛，他们的不同点只在最后一位不同，我们可再利用异或来消除这个差异。
所以，两者的判别条件是

(((j-1)>>(i-1))^1)==((k-1)>>(i-1))

有了这个判别式我们可以进行概率dp来得到转移方程，记表示进行到第轮，获胜的概率，那么有，表示和都活到了第的概率再乘上战胜的概率。
最后输出即可。

复杂度

时间复杂度为

代码

#include <bits/stdc++.h>
using namespace std;
const int N=1030;
double p[N][N];
double dp[N][N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int len=(1<<n);
    for(int i=1;i<=len;i++)
        for(int j=1;j<=len;j++)
    {
        scanf("%lf",&p[i][j]);
        p[i][j]/=100.0;
    }
    for(int i=1; i<=len; i++)
        dp[0][i]=1;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=len; j++)
            for(int k=1; k<=len; k++)
                if((((j-1)>>(i-1))^1)==((k-1)>>(i-1)))
                {
                    dp[i][j]+=dp[i-1][j]*p[j][k]*dp[i-1][k];
                }
    printf("%.10lf\n",dp[n][m]);
    return 0;
}