#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
ll f[85][25][1<<8], cnum[85][25];
int state[300], num[300];
bool check(int x){
bool flag=false;
while(x){
if(!flag) flag=(x&1);
else if(x&1) return false;
x=x>>1;
}
return true;
}
bool check2(int x, int y){
while(x&&y){
if((x&1)&&(y&1)) return false;
x=x>>1; y=y>>1;
}
return true;
}
int getnum(int x){
int ret=0;
while(x){
if(x&1) ret++;
x=x>>1;
}
return ret;
}
ll gcd(ll x, ll y){
if(y==0) return x;
return gcd(y, x%y);
}
ll c(ll x, ll y){
if(y==0||x==y) return 1;
if(x==0) return 0;
if(cnum[x][y]!=-1) return cnum[x][y];
return cnum[x][y]=c(x-1, y)+c(x-1, y-1);
}
int main(){
int n, m, k, cnt=0; cin>>n>>m>>k;
if(n>m) swap(n, m);
if(k==0){ cout<<"1/1"<<endl; }
int p=1<<n;
f[0][0][0]=1;
for(int i=0;i<p;i++) if(check(i)){ state[++cnt]=i; num[cnt]=getnum(i); }
for(int i=1;i<=m;i++)
for(int l=1;l<=cnt;l++){
f[i][num[l]][state[l]]=1;
for(int j=num[l]+1;j<=k;j++)
for(int g=1;g<=cnt;g++)
if(check2(state[l], state[g]))
f[i][j][state[l]]+=f[i-1][j-num[l]][state[g]];
}
ll tot=0;
for(int i=1;i<=cnt;i++) tot+=f[m][k][state[i]];
if(!tot){ cout<<"Impossible!"<<endl; return 0; }
memset(cnum, -1, sizeof(cnum));
ll tmp=c(n*m, k);
ll d=gcd(tot, tmp);
tot/=d; tmp/=d;
cout<<tmp<<'/'<<tot<<endl;
return 0;
}
好吧解决了
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
ll f[85][25][1<<8], cnum[85][25];
int state[300], num[300];
bool check(int x){
while(x){
if((x&3)==3) return false;
x=x>>1;
}
return true;
}
bool check2(int x, int y){
while(x&&y){
if((x&1)&&(y&1)) return false;
x=x>>1; y=y>>1;
}
return true;
}
int getnum(int x){
int ret=0;
while(x){
if(x&1) ret++;
x=x>>1;
}
return ret;
}
ll gcd(ll x, ll y){
if(y==0) return x;
return gcd(y, x%y);
}
ll c(ll x, ll y){
if(y==0||x==y) return 1;
if(x==0) return 0;
if(cnum[x][y]!=-1) return cnum[x][y];
return cnum[x][y]=c(x-1, y)+c(x-1, y-1);
}
int main(){
int n, m, k, cnt=0; cin>>n>>m>>k;
if(n>m) swap(n, m);
if(k==0){ cout<<"1/1"<<endl; }
int p=1<<n;
f[0][0][0]=1;
for(int i=0;i<p;i++) if(check(i)){ state[++cnt]=i; num[cnt]=getnum(i); }
for(int i=1;i<=m;i++)
for(int l=1;l<=cnt;l++){
f[i][num[l]][state[l]]=1;
for(int j=num[l]+1;j<=k;j++)
for(int g=1;g<=cnt;g++)
if(check2(state[l], state[g]))
f[i][j][state[l]]+=f[i-1][j-num[l]][state[g]];
}
ll tot=0;
for(int i=1;i<=cnt;i++) tot+=f[m][k][state[i]];
if(!tot){ cout<<"Impossible!"<<endl; return 0; }
memset(cnum, -1, sizeof(cnum));
ll tmp=c(n*m, k);
ll d=gcd(tot, tmp);
tot/=d; tmp/=d;
cout<<tmp<<'/'<<tot<<endl;
return 0;
}