Description

N 个男孩，N 个女孩，男孩和女孩可能是朋友，也可能不是朋友。现在要组成N 对舞伴，要求每对舞

伴都是一男一女，且他们是朋友。

统计不同配对方案的数量，因为结果很大，所以只要求除以M 的余数。

Input

第1 行，2 个整数N，M。接下来N 行，每行N 个整数Aij，表示第i 个男孩和第j 个女孩的关系。如果他们是朋友，则Aij = 1，否则Aij = 0。

Output

1 个整数，表示所求的值。

Sample Input

3 1000000000

1 1 1

1 1 1

1 1 1

Sample Output

6

Data Constraint

• 对于50% 的数据，N <= 9；

• 对于100% 的数据，1 <= N <= 20， 1 <= M <= 10^9; 0 <= Aij <= 1。

题解

快速过了一遍题目，瞟了一眼n<=20咦！完全存得下2^20，然后就走上了一条不归路一开始码题时，怕强行被数据卡不过，小心翼翼的打起来只有一维的方程(设f[x]为当前女生匹配的状态为x的方案数）后面越码越不对劲，想来想去没有思路怎么去转移方程，整个人都虚了无奈之下。。只好ctrl A+ctrl x,重新推二维的转移方程结果，几下就推出来了，还算了算复杂度发现只是O（n（n+(1<
     
      <
     

代码

#include
     
      #include
      
       int x,n,m,a[21],two[21],f[2][1<<20],w,l;using namespace std;int main(){    freopen("perm.in","r",stdin);    freopen("perm.out","w",stdout);    scanf("%d%d",&n,&m);    two[0]=1; f[0][0]=1;    for(int i=1;i<=n;i++) two[i]=two[i-1]*2;    for(int i=1;i<=n;i++)    {        x=1^x;        l=0;        memset(f[x],0,sizeof(f[x]));        for(int j=1;j<=n;j++)         {            scanf("%d",&w);            if (w==1) a[++l]=j;        }        for(int s=0;s