分析

求一个$n\times m$棋盘中随机放置$pn$个棋子两两不相邻的期望次数。

首先不计相邻的总方案次数为$C^{n\times m}_{pn}$。

定义$f[i][j][k]$为第$i$行的状态为$j$,前$i$行还剩$k$个棋子没放,设计状态转移方程。

可以将$n​$和$m​$的值对调保证$n>m​$以尽可能降低状态压缩的时间复杂度和空间复杂度。

还要预处理出一行所有不相邻的状态和耗费的棋子数,来提高动态规划时的时间效率。

由于内存使用较大,可以利用滚动数组优化空间复杂度。

最后除去相邻情况的方案数为$\sum^{2^m-1}_{j=0}{f[n][j][0]}(j<<1\&j==0)​$。

两数利用辗转相除法约分即可输出结果。

代码(Accepted)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <algorithm>
#include <vector>
typedef long long int ll;
int gcd(ll a,ll b) {
return b==0?a:gcd(b,a%b);
}
inline ll c(int n,int m) {
ll c=1;
for(int k=1;k<=m;++k) {
c=c*(n-k+1)/k;
}
return c;
}
int n,m,pn;
ll f[2][1<<10][21];
std::vector<int> state;
std::vector<int> cnt;
int main() {
scanf("%d%d%d",&n,&m,&pn);
if(n<m) std::swap(n,m);
int temp;
for(int i=0;i<(1<<m);++i) {
if(((i<<1)&i)==0) {
temp=0;
for(int j=0;j<m;++j) {
if((i>>j)&1) ++temp;
}
state.push_back(i);
cnt.push_back(temp);
}
}
for(unsigned int i=0;i<state.size();++i) {
if(pn-cnt[i]>=0) f[0][i][pn-cnt[i]]=1;
}
for(int i=2;i<=n;++i) {
for(unsigned int j=0;j<state.size();++j) {
for(int k=0;k+cnt[j]<=pn;++k) {
f[(i+1)%2][j][k]=0;
for(unsigned int l=0;l<state.size();++l) {
if((state[j]|state[l])==(state[j]^state[l])) {
f[(i+1)%2][j][k]+=f[i%2][l][k+cnt[j]];
}
}
}
}
}
ll x=c(n*m,pn),y=0;
for(unsigned int i=0;i<state.size();++i) {
y+=f[(n+1)%2][i][0];
}
int g=gcd(x,y);x/=g;y/=g;
printf("%lld/%lld\n",x,y);
return 0;
}