题解：P10267 机器人
wwt100127
·
·
题解
思路
期望 DP。
分成撞不撞墙两种可能。
设 Arrive_{i,j} 表示从 (1,1) 出发，走 i+j-2 步，到达 (i,j) 的概率。
则撞墙的期望就是 x \times (1-Arrive_{i,j})。
接下来考虑不撞墙的情况。
如果直接 DP，比较困难。因为是异或操作，可以考虑将每一位分开计算。
对于第 k 位，设 dp_{i,j} 表示从 (1,1) 出发，到达 (i,j)，第 k 位异或是 1 的概率。
如果 a_{i,j} 的第 k 位是 0，则要使异或后使 1，只需要让上一个位置异或完是 1，即：
dp_{i,j} = dp_{i-1,j} + dp_{i,j-1}
同理，如果 a_{i,j} 的第 k 位是 1，则要使异或后使 1，只需要让上一个位置异或完是 0。
所以此时：
$$
dp_{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;
}
```