Swap - ShinriiTin's Blog - 博主是sb
codeforces 442D Adam and Tree
codeforces 455E Function

Swap

ShinriiTin posted @ 2015年6月15日 20:31 in 未分类 with tags 概率与期望 某不科学的三千元系列 , 683 阅读

题意:

给出一个n*m(n<=103,m<=103)的黑白棋棋盘.

棋盘上有t(t<=105)个位置坏掉了。

除了坏掉的位置之外,每个位置上有且只有1颗棋子,且初始时白面向上。

你可以进行k(k<=109)次操作。

每次操作选择两颗棋子,将以它们为对角线的矩形内的所有棋子状态取反(不一定是主对角线).

问k次操作后,白面向上的棋子个数的期望值是多少。

 

分析:

由于期望具有线性性,我们可以分别计算每颗棋子的期望最后再求和。

假设某颗棋子在1次操作中被翻转的概率为p。

那么容易推出它k次操作后状态不变的概率为(1+(1-2*p)k)/2.

现在问题就在于如何快速求出p.

由容斥得(x,y)被翻转的情况有:

|([1,x]×[1,y],[x,y]×[n,m])|+|([x,n]×[1,y],[1,x]×[y,m])|-|([x,x]×[1,y],[x,x]×[y,m])|-|([1,x]×[y,y],[x,n]×[y,y])|+1

用前缀和优化就好了。

 

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define g() getchar()
template<class Q>void Scan(Q&x){
	char c;while(c=g(),c<48||c>57);
	for(x=0;c>47&&c<58;c=g())x=10*x+c-48;
}

#define rep(i,a,b) for(int i=a;i<b;++i)

const int MAXN=1005;

int n,m,k,t;

bool a[MAXN][MAXN];

int sum[MAXN][MAXN];

inline int Sum(int x1,int y1,int x2,int y2){
	int res=sum[x2][y2]-sum[x2][y1-1];
	return res-(sum[x1-1][y2]-sum[x1-1][y1-1]);
}

inline void Init(){
	Scan(n),Scan(m),Scan(k),Scan(t);
	rep(i,1,n+1)rep(j,1,m+1)sum[i][j]=a[i][j]=1;
	rep(i,1,t+1){
		int x,y;
		Scan(x),Scan(y);
		sum[x][y]=a[x][y]=0;
	}
	rep(i,1,n+1)rep(j,1,m+1)sum[i][j]+=sum[i][j-1];
	rep(i,1,n+1)rep(j,1,m+1)sum[i][j]+=sum[i-1][j];
}

typedef long double ld;
typedef long long ll;

inline ld qpow(ld x,int k){
	ld ans=1;
	for(;k;x=x*x,k>>=1)
		if(k&1)ans=ans*x;
	return ans;
}

ld ans;

inline void Solve(){
	ll q=1ll*sum[n][m]*sum[n][m];
	rep(i,1,n+1)rep(j,1,m+1){
		if(!a[i][j])continue;
		ll p=1ll*Sum(1,1,i,j)*Sum(i,j,n,m)+1ll*Sum(1,j,i,m)*Sum(i,1,n,j);
		p-=1ll*Sum(i,1,i,j)*Sum(i,j,i,m)+1ll*Sum(1,j,i,j)*Sum(i,j,n,j);
		p=p<<1|1;
		ld pr=(ld)p/q;
		ans+=(qpow(1.-pr*2.,k)+1.)/2.;
	}
	printf("%.20f\n",(double)ans);
}

int main(){
	freopen("swap.in","r",stdin);
	freopen("swap.out","w",stdout);
	Init(); Solve(); return 0;
}
 
Avatar_small
Emma 说:
2023年1月21日 00:30

This fascinating problem challenges us to calculate the expected value of the number of chess pieces with the white side up on a Reversi board of n*m dimensions. This task is complicated by the presence of t broken positions, as well as peter veres photography artist the ability to perform up to k operations, each of which inverts the state of all chess pieces in a rectangular area with two chosen chess pieces as the diagonal. Solving this problem requires an astute understanding of mathematical principles and could offer some interesting insights into the field of game theory.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter