ASSIGN - Assignments
Problem
Your task will be to calculate number of different assignments of n different topics to n students such that everybody gets exactly one topic he likes.
Input
First line of input contains number of test cases c (1<=c<=80). Each test case begins with number of students n (1<=n<=20). Each of the next n lines contains n integers describing preferences of one student. 1 at the ith position means that this student likes ith topic, 0 means that he definitely doesn't want to take it.
Output
For each test case output number of different assignments (it will fit in a signed 64-bit integer).
Example
Input:
3
3
1 1 1
1 1 1
1 1 1
11
1 0 0 1 0 0 0 0 0 1 1
1 1 1 1 1 0 1 0 1 0 0
1 0 0 1 0 0 1 1 0 1 0
1 0 1 1 1 0 1 1 0 1 1
0 1 1 1 0 1 0 0 1 1 1
1 1 1 0 0 1 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 1
1 0 1 1 0 0 0 0 0 0 1
0 0 1 0 1 1 0 0 0 1 1
1 1 1 0 0 0 1 0 1 0 1
1 0 0 0 1 1 1 1 0 0 0
11
0 1 1 1 0 1 0 0 0 1 0
0 0 1 1 1 1 1 1 1 1 1
1 1 0 1 0 0 0 0 0 1 0
0 1 0 1 0 1 0 1 0 1 1
1 0 0 1 0 0 0 0 1 0 1
0 0 1 0 1 1 0 0 0 0 1
1 0 1 0 1 1 1 0 1 1 0
1 0 1 1 0 1 1 0 0 1 0
0 0 1 1 0 1 1 1 1 1 1
0 1 0 0 0 0 0 0 0 1 1
0 1 1 0 0 0 0 0 1 0 1 Output:
6
7588
7426
利用二进制表示集合，f[S][i]表示i个人形成S状态的座位的方案个数，答案就是 f[all][n], 注意爆int。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
long long f[][(<<)+];
int e[][];
int main()
{
int t,n,m,i,j,k;
cin>>t;
while(t--){
cin>>n;
for(i=;i<=n;++i)
for(j=;j<=n;++j) cin>>e[i][j];
memset(f,,sizeof(f));
f[][]=;
int cur=;
for(i=;i<=n;++i){
cur^=;
memset(f[cur],,sizeof(f[cur]));
for(j=;j<(<<n);++j){
if(!f[cur^][j]) continue;
for(k=;k<=n;++k){
if(e[i][k]&& ((<<(k-))&j)==) {
f[cur][j|(<<(k-))]+=f[cur^][j];
}
}
}
/*for(j=0;j<(1<<n);++j){
cout<<j<<' '<<f[cur][j]<<endl;
}*/
}
cout<<f[cur][(<<n)-]<<endl;
}
return ;
}