CodeForces 717D

D Dexterina’s Lab

题面

time limit per test:1 second

memory limit per test:256 megabytes

input:standard input

output:standard output

Dexterina and Womandark have been arch-rivals since they’ve known each other. Since both are super-intelligent teenage girls, they’ve always been trying to solve their disputes in a peaceful and nonviolent way. After god knows how many different challenges they’ve given to one another, their score is equal and they’re both desperately trying to best the other in various games of wits. This time, Dexterina challenged Womandark to a game of Nim.

Nim is a two-player game in which players take turns removing objects from distinct heaps. On each turn, a player must remove at least one object, and may remove any number of objects from a single heap. The player who can’t make a turn loses. By their agreement, the sizes of piles are selected randomly from the range [0, x]. Each pile’s size is taken independently from the same probability distribution that is known before the start of the game.

Womandark is coming up with a brand new and evil idea on how to thwart Dexterina’s plans, so she hasn’t got much spare time. She, however, offered you some tips on looking fabulous in exchange for helping her win in Nim. Your task is to tell her what is the probability that the first player to play wins, given the rules as above.

Input

The first line of the input contains two integers n (1 ≤ n ≤ $10^9$) and x (1 ≤ x ≤ 100) — the number of heaps and the maximum number of objects in a heap, respectively. The second line contains x + 1 real numbers, given with up to 6 decimal places each:P(0), P(1), … , P(X). Here, P(i) is the probability of a heap having exactly i objects in start of a game. It’s guaranteed that the sum of all P(i) is equal to 1.

Output

Output a single real number, the probability that the first player wins. The answer will be judged as correct if it differs from the correct answer by at most $10^{-6}$.

Sample Input

1
2
2 2
0.500000 0.250000 0.250000

Sample Output

1
0.62500000

题目大意

给定Nim博弈问题,有n堆石子,每人每次选定一堆取至少一颗石子,不能取者判负。

每堆石子数目独立,个数范围从0~x,概率分别为P(0)~P(x)。

问先手胜利的概率。

思路

首先这是一个标准的Nim博弈问题,决定先手必胜或者是必败的仅仅是所有石子的异或(Xor)和。

在这题中,Xor和为0则先手必败,否则先手必胜。

我们可以计算出先手必败的概率,拿1去减即可,问题不大。

那么问题转化为如何去计算Xor和为0的概率?

显然这个可以由递推得到:

​ 我们假设$A_{i,j}$表示前$i$堆石子,Xor和为$j$的概率

​ 那么得到如下的递推公式:

​ $A_{i,j}=\sum_{x\ xor\ y=j}A_{i-1,x}*P(y)$ ($x$和$y$之间有序)

​ 需要注意的是Xor和的上界,当$x$最大为100时,所有数的Xor和不会超过127(具体原因可以自己想想)

到这问题已经解决了一半,那么哪里出了问题呢?

看了一眼数据范围,GG!

如果使用递推公式的话,那么时间复杂度已经可以得出$O(n{x^2})$,考虑到$n$那$10^9$的数据范围,这样做显然会超时。

自然而然的,我们就联想到了加速递推公式的最佳工具—快速幂

这里快速幂的矩阵构造需要想清楚,我被卡了好一会才理清了关系。

还是使用$A_{i,j}$表示前$i$堆Xor和为$j$的概率,$M$表示矩阵。

那么向下一堆递推的时候,如果使用矩阵乘法应该怎样做呢?

$A_{i+1,j}=\sum_{k=0}^tA_{i,k}*M_{k,j}​$($t​$表示枚举上界)

假设放置于$M_{j,k}$位置的概率为$P(s)$,那么显然$k\ xor\ j=s$,这样s就被计算了出来。

总结一下,对于需做快速幂的矩阵$M$,$M_{i,j}=P(i\ xor\ j)$

需要注意的是有个预处理的小细节,$A_{1,j}=P(j)$,因此快速幂作$n-1$次即可

使用快速幂之后的时间复杂度为$O({x^3}logn)$,这样的复杂度即使是1s的时间限制,考虑到CF强大的评测机也基本可以AC。

至此,问题得以完美解决。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <deque>
#include <bitset>
#include <algorithm>

using namespace std;

const double eps=1e-10;
const double pi=3.1415926535897932384626433832795;
const double eln=2.718281828459045235360287471352;

#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define scan2(x, y) scanf("%d%d", &x, &y)
#define scan3(x, y, z) scanf("%d%d%d", &x, &y, &z)
#define sqr(x) (x) * (x)
#define pr(x) printf("Case %d: ",x)
#define prn(x) printf("Case %d:\n",x)
#define prr(x) printf("Case #%d: ",x)
#define prrn(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

struct mat
{
int n;
double m[130][130];

mat operator * (struct mat b)const
{
struct mat ans;
ans.n=n;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)ans.m[i][j]=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
for(int k=0;k<=n;k++)
ans.m[i][j]+=m[i][k]*b.m[k][j];
return ans;
}

mat operator + (struct mat b)const
{
struct mat ans;
ans.n=n;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)ans.m[i][j]=0;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)ans.m[i][j]=m[i][j]+b.m[i][j];
return ans;
}

mat operator ^ (int t)const
{
struct mat ans,p;
ans.n=p.n=n;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)p.m[i][j]=m[i][j];
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
if(i==j)ans.m[i][j]=1;else ans.m[i][j]=0;
while(t>0)
{
if(t&1)ans=ans*p;
p=(p*p);
t=t>>1;
}
return ans;
}

};

int main()
{
int i,j,n,m;
double a[130];
scanf("%d %d",&n,&m);
memset(a,0,sizeof(a));
struct mat xs;
xs.n=127;
for(i=0;i<=m;i++)scanf("%lf",&a[i]);
for(i=0;i<=127;i++)
for(j=0;j<=127;j++)
xs.m[i][j]=a[i^j];
struct mat ans=xs^(n-1);
double tot=1;
for(i=0;i<=m;i++)tot-=a[i]*ans.m[i][0];
printf("%.8lf",tot);
return 0;
}