Dexterina’s Lab，动态规划+矩阵快速幂

我不是女神ヾ 2022-10-15 00:43 2阅读 0赞

[链接][Link 1]

### Dexterina’s Lab ###

*  大意
 *  思路
 *  code1
 *  code2

# 大意 #

**题面**  
给定若干个堆，两人每次从一个堆中拿一个或者多个东西，最后没有东西拿的人输

**输入**  
n： 堆的数量， 1   ≤   n   ≤   1 0 9 1 ≤ n ≤ 10^9 1 ≤ n ≤ 109  
x： 一个堆中所含东西的最大数量，只能从 \[ 0 , x \] \[0 ,x\] \[0,x\]选  
输入 x+1 个数：  
P(0), P(1), … , P(X), 其中P(i) 表示一个堆恰有 i 个东西的概率

**输出**  
先手赢的概率

# 思路 #

前 i 堆石子XOR 和为x，转移方程：

d p \[ i \] \[ x \] = d p \[ i − 1 \] \[ x X O R 0 \] ∗ p 0 + d p \[ i − 1 \] \[ x X O R 1 \] ∗ p 1 + . . . + d p \[ i − 1 \] \[ x X O R n \] ∗ p n dp\[i\]\[x\]=dp\[i-1\]\[xXOR0\]\*p\_0+dp\[i-1\]\[x XOR 1\]\*p\_1+...+dp\[i-1\]\[xXORn\]\*p\_n dp\[i\]\[x\]=dp\[i−1\]\[xXOR0\]∗p0\+dp\[i−1\]\[xXOR1\]∗p1\+...\+dp\[i−1\]\[xXORn\]∗pn

1   ≤   n   ≤   1 0 9 1 ≤ n ≤ 10^9 1 ≤ n ≤ 109，数据量大，log(n) 的算法才能过

由于 X O R XOR XOR和不会超过127，可以构造一个128\*128的矩阵

# code1 #

#include <bits/stdc++.h>
    using namespace std;
    const int m = 128;
    int n, x;
    double p[m];
    
    struct Mat
    { 
    	double num[m][m];
    };
    
    Mat mul(Mat a, Mat b)
    { 
    	Mat ans;
    	for(int i = 0; i < m; i ++)
    		for (int j = 0; j < m; ++j)
    		{ 
    			ans.num[i][j] = 0;
    			for (int k = 0; k < m; ++k)
    				ans.num[i][j] += a.num[i][k] * b.num[k][j]; 
    		}
    	return ans;
    }
    
    Mat Pow(Mat a, int k)
    { 
    	Mat ans;
    
    	memset(ans.num, 0, sizeof(ans.num));
    	for(int i = 0; i < m; i++) ans.num[i][i] = 1;
    
    	while(k)
    	{ 
    		if(k&1) ans = mul(ans, a);
    		a =  mul(a, a);
    		k >>= 1;
    	}
    	return ans;
    }
    
    
    Mat A;
    int main()
    { 
        scanf("%d %d", &n, &x);
    	{ 
    		for(int i = 0; i < x; i++) scanf("%lf", p+i);
    		for(int i = 0; i < m; i++)
    			for(int j = 0; j < m; j++)
    				A.num[i][j] = p[i^j];
    		A = Pow(A, n);
    		printf("%.10lf\n", 1 - A.num[0][0]);
    	}
    	return 0;
    }

# code2 #

#include <bits/stdc++.h>
    using namespace std;
    const int m = 128;
    int n, x;
    double p[m];
    
    struct Mat
    { 
    	double num[m][m];
    };
    
    Mat mul(Mat a, Mat b)
    { 
    	Mat ans;
    	for(int i = 0; i < m; i ++)
    		for (int j = 0; j < m; ++j)
    		{ 
    			ans.num[i][j] = 0;
    			for (int k = 0; k < m; ++k)
    				ans.num[i][j] += a.num[i][k] * b.num[k][j]; 
    		}
    	return ans;
    }
    
    Mat Pow(Mat a, int k)
    { 
    	Mat ans;
    
    	memset(ans.num, 0, sizeof(ans.num));
    	for(int i = 0; i < m; i++) ans.num[i][i] = 1;
    
    	while(k)
    	{ 
    		if(k&1) ans = mul(ans, a);
    		a =  mul(a, a);
    		k >>= 1;
    	}
    	return ans;
    }
    
    
    Mat A;
    int main()
    { 
        scanf("%d %d", &n, &x);
    	{ 
    		for(int i = 0; i < x; i++) scanf("%lf", p+i);
    		for(int i = 0; i < m; i++)
    			for(int j = 0; j < x; j++)
    				A.num[i][j^i] = p[j];
    		A = Pow(A, n);
    		printf("%.10lf\n", 1 - A.num[0][0]);
    	}
    	return 0;
    }

[Link 1]: https://codeforces.com/group/vFwRVj9WjO/contest/328371/problem/J