棋盘 chess

Description

给出一张 n × n 的棋盘，格子有黑有白。现在要在棋盘上放棋子，要求：
• 黑格子上不能有棋子
• 每行每列至多只有一枚棋子
你的任务是求出有多少种合法的摆放方案。答案模

Input

输入的第一行一个整数 n ( n ≤ 15) 。
接下来一个 n × n 的棋盘( 1 表示黑；0 表示白)。

Output

输出一行一个整数，表示合法方案数对

Sample Input

12
000010000000
000000000000
000010011000
001000011011
011000100111
000010110000
101000010001
000001000000
110000000000
000000000010
010010110100
011010010100

Sample Output

349847765

题解：

水题，放松心情 F[i][j] 前i行,列状态为j的状态数

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 using namespace std;
 8 typedef long long ll;
 9 const int N=16,mod=1e9+7;
10 ll f[N][1<<15];char s[N];bool d[N][N];
11 int main()
12 {
13     int n;
14     scanf("%d",&n);
15     for(int i=1;i<=n;i++){
16         scanf("%s",s);
17         for(int j=0;j<n;j++)if(s[j]=='0')d[i][j+1]=true;
18     }
19     f[0][0]=1;
20     int to=(1<<n)-1,t;
21     for(int i=1;i<=n;i++){
22         for(int j=0;j<=to;j++){
23             f[i][j]+=f[i-1][j];
24             f[i][j]%=mod;
25             for(int k=1;k<=n;k++){
26                 t=(1<<(k-1));
27                 if(d[i][k] && !(t&j)){
28                     f[i][j|t]+=f[i-1][j];
29                     f[i][j|t]%=mod;
30                 }
31             }
32         }
33     }
34     ll ans=0;
35     for(int j=0;j<=to;j++)
36         ans+=f[n][j],ans%=mod;
37     printf("%lld
",ans);
38     return 0;
39 }