NC213993. WZB'sHarem
描述
Do you remember N-queens? Today, WZB accompanied his n queens to the cinema……
As the saying goes: Three queens for a play, one harem admits of no two queens…
Cinema uses n rows of seats, each row has n columns.Queens are grumpy, they're not willing to sit in the same row or same column with other queen, if there are two queens in the same row or same column they conflict occurs, so they make WZB arrange seats for them. It stumped WZB to avoid the queen make antinomy. WZB wants to know how many different arrangements there are for the queen, he'd like to choose one for them.
Since WZB and his queens arrived late, some seats had already been reserved by others. Although WZB is a king, he can't infringe on the rights of citizens, so the reserved seats could not be reserved for queens.
Now WZB has ordered you to work out how many ways to arrange the queen. If WZB finds out your calculations are wrong....
输入描述
There is an integer n(n<=20) in the firstline. The cinema has n rows and n columns of seats.
In the next lines,there are n integers ineach line(0 or 1).If the point(i,j) is 1, it means it has been booked.
输出描述
One integer.You just need to print the answer Mod 1000000007.
示例1
输入:
2 0 0 0 0
输出:
4
C++(clang++11) 解法, 执行用时: 143ms, 内存消耗: 45560K, 提交时间: 2020-12-10 19:34:43
#include<bits/stdc++.h>
using namespace std;
const int N=20;
int dp[21][1<<N];
bool G[N+1][N];
int main(){
int n;cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>G[i][j];
}
}
dp[0][0]=1;
const int P=1e9+7;
for(int i=0;i<n;i++){
for(int st=0;st<(1<<n);st++){
if(dp[i][st]){
for(int j=0;j<n;j++){
if(st&(1<<j)||G[i][j])continue;
(dp[i+1][st|(1<<j)]+=dp[i][st])%=P;
}
}
}
}
int ans=dp[n][(1<<n)-1];
for(int i=2;i<=n;i++){
ans=1ll*ans*i%P;
}
cout<<ans;
}