- 座位安排
- 2017-09-03 16:53:59 @
#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;
}
1 条评论
-
eurus LV 8 @ 2017-09-03 17:53:04
好吧解决了
#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; }
- 1