P9268 题解

· · 题解

题目里给的步数可以认为是无穷。但是这是个偶数，所以如果起始与结束状态奇偶性都不一样直接输出 0。

现在考虑下奇偶性一样的情况。由于走了无穷步，所以棋盘中中间的格子，边上的格子，角上的格子可以认为是互相等价的。或者说，相邻的格子数量相等的格子是等价的。这样的话，我们计算下结束前一步有多少种走到结束状态的本质不同的方法，注意这里本质不同是指最后一步走的方法不一样而不是棋子位置不一样。再除以最后一步的总方案数就可以了。这样看起来是错的，但实际上很合理。虽然有一些状态，棋子们相对靠近中间，到达这个状态的概率会高一些，但是下一步，这种状态可选的走法也更多，平均下来每种本质不同的走法其实概率是一样的。

具体的计算方法的话，首先奇偶性判断只需要将横纵坐标求和判断奇数还是偶数。然后计算最后一步可以达到最终状态的方案数，先枚举最后一步挪动了哪个棋子，然后枚举从哪个方向过来，然后其余的棋子位置要求与最终状态一样，所以枚举完这两点之后有且仅有一种方案合法。总共的方案数也是先枚举这两点，但是这时其他棋子可以任意摆放，有 \binom{nm-2}{k-1} 种合法方案。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
#define fi first
#define se second
int n,m,k;
char c[10][10];
const pii d[4]={{-1,0},{0,1},{1,0},{0,-1}};
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    int sum1=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c[i][j];
            if(c[i][j]=='O'){
                k++;
                sum1+=i+j;
            }
        }
    }
    int sum2=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c[i][j];
            if(c[i][j]=='O'){
                sum2+=i+j;
            }
        }
    }
    if(sum1%2!=sum2%2)return cout<<0,0;//判断奇偶性
    int fz=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(c[i][j]=='O'){
                for(int a:{0,1,2,3}){
                    int x=i+d[a].fi,y=j+d[a].se;
                    if(x>=1&&x<=n&&y>=1&&y<=m&&c[x][y]=='.')fz++;
                }
            }
        }
    }
    int c=1;
    for(int i=0;i<k-1;i++)c*=n*m-2-i;
    for(int i=1;i<=k-1;i++)c/=i;
    // cerr<<c<<endl;
//计算组合数 C(n*m-2,k-1)
    int fm=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int deg=0;
            for(int a:{0,1,2,3}){
                int x=i+d[a].fi,y=j+d[a].se;
                if(x>=1&&x<=n&&y>=1&&y<=m)deg++;
            }
//上一步总共的方案数，枚举i,j表示最后一步动了哪个位置的棋子，a枚举向哪个方向动，
//确定了这两点之后其他位置上任意放其余的棋子。
            fm+=deg*c;
        }
    }
    // assert(fm%2==0);
    fm/=2;
//别忘了上一步的奇偶性必须不同于结束状态，所以要减半。
    cout<<fixed<<setprecision(13)<<1.0*fz/fm;
    return 0;
}