专栏文章

题解：P10267 机器人

wwwt100127
P10267题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipqwj6f
此快照首次捕获于
2025/12/03 16:28
3 个月前
此快照最后确认于
2025/12/03 16:28
3 个月前
查看原文

思路

期望 DP。
分成撞不撞墙两种可能。
设 Arrivei,jArrive_{i,j} 表示从 (1,1)(1,1) 出发，走 i+j−2i+j-2 步，到达 (i,j)(i,j) 的概率。 则撞墙的期望就是 x×(1−Arrivei,j)x \times (1-Arrive_{i,j})。
接下来考虑不撞墙的情况。
如果直接 DP，比较困难。因为是异或操作，可以考虑将每一位分开计算。
对于第 kk 位，设 dpi,jdp_{i,j} 表示从 (1,1)(1,1) 出发，到达 (i,j)(i,j)，第 kk 位异或是 11 的概率。
如果 ai,ja_{i,j} 的第 kk 位是 00，则要使异或后使 11，只需要让上一个位置异或完是 11，即：
dpi,j=dpi−1,j+dpi,j−1dp_{i,j} = dp_{i-1,j} + dp_{i,j-1}
同理，如果 ai,ja_{i,j} 的第 kk 位是 11，则要使异或后使 11，只需要让上一个位置异或完是 00。
异或完是 0 的概率 = 到达此地的概率 - 异或完是 1 的概率\text{异或完是 0 的概率 = 到达此地的概率 - 异或完是 1 的概率}。
所以此时：
dpi,j=Arrivei−1,j−dpi−1,j+Arrivei,j−1−dpi,j−1dp_{i,j} = Arrive_{i-1,j} - dp_{i-1,j} + Arrive_{i,j-1} - dp_{i,j-1}
将答案累加即可。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
bool Beginning;

#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define se second
#define fi first
using PII=pair<int,int>;
using PIB=pair<int,bool>;
using PBI=pair<bool,int>;
using PBB=pair<bool,bool>;
using PDI=pair<double,int>;
using PID=pair<int,double>;

const int mod=1e9+7;
namespace Memory_Love{
	int read(){ int x=0; bool flag=1; char ch=getchar();
		while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
		while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return flag? x:-x;}
	template<typename T> void read(T &x){ bool flag=1; x=0; char ch=getchar();
		while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
		while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} x=(flag? x:-x);}
	template<typename T,typename ...Args> void read(T &Re,Args &...Res){read(Re),read(Res...);}
	template<typename T> void write(T x,char ch=0){if(x<0) x=-x,putchar('-');
		static short s[35],top=-1; do{s[++top]=x%10;x/=10;}while(x);
		while(~top) putchar(s[top--]+48); if(ch) putchar(ch);}
	int gcd(int a,int b){return b==0? a:gcd(b,a%b);}
	int lcm(int a,int b){return a/gcd(a,b)*b;}
	int lowbit(int x){return (x&-x);}
	void MADD(int &x,int y,int mod){x=(x+y>=mod? x+y-mod:x+y);}
	int ksc(int a,int b,int p){int ans=0;while(b){if(b&1)MADD(ans,a,p);MADD(a,a,p);b>>=1;}return ans;}
	int ksm(int a,int b,int p){int ans=1%p;while(b){if(b&1)ans=ans*a%p;a=a*a%p;b>>=1;}return ans;}
	int exgcd(int a,int b,int &x,int &y){if(b==0){x=1,y=0;return a;}int d=exgcd(b,a%b,y,x);y-=a/b*x;return d;}
	int inv(int t){int x,y;exgcd(t,mod,x,y);return (x%mod+mod)%mod;}
} using namespace Memory_Love;
const int N=1e3+5;
const int M=30;
const int inv2=inv(2);
int n,m,Wrong;
int a[N][N];
int dp[N][N];
int Arrive[N][N];

int P(int i,int j,int x){return (x==1? dp[i][j]:(Arrive[i][j]-dp[i][j]));}
int DP(int k)
{
	int i,j;
	memset(dp,0,sizeof(dp));
	dp[1][1]=(a[1][1]>>k&1);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			int x=(a[i][j]>>k&1);
			if(i!=1 || j!=1)
			dp[i][j]=(P(i-1,j,x^1)+P(i,j-1,x^1))*inv2%mod;
		}
	}
	return dp[n][m];
}

bool Ending;
signed main()
{
	int i,j,ans=0;
	read(n,m,Wrong);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		a[i][j]=read();
	}
	
	Arrive[1][1]=1;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(i!=1 || j!=1)
			Arrive[i][j]=(Arrive[i-1][j]+Arrive[i][j-1])*inv2%mod;
		}
	}
	(ans+=(1-Arrive[n][m])*Wrong)%=mod;
	
	for(i=0;i<=M;i++)
	(ans+=(1<<i)*DP(i))%=mod;
	
	write((ans+mod)%mod,'\n');
	
	
	cerr<<"\nused:"<<(abs(&Ending-&Beginning)/1048576)<<"MB\n";
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...