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。

Solution

• 這題一看 N≤20 就知道是狀壓DP啦！

• 設 f[i][s] 表示選了前 i 個男孩，已選女孩狀態為 s 的方案數。

• 顯然可得：f[i][s]+=f[i?1][s′]

• 每個男孩向是朋友的女孩轉移即可，還可以開滾動節約空間。

• 總時間復雜度為 O(2N?N2) 。

Code

#include<cstdio> #include<cstring> using namespace std; int roll; int a[21],p[21]; int f[2][1<<20]; inline int read() {int data=0; char ch=0;while(ch<'0' || ch>'9') ch=getchar();while(ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data; } int main() {int n=read(),m=read();for(int i=p[0]=1;i<=n;i++) p[i]=p[i-1]*2;for(int i=f[0][0]=1;i<=n;i++){roll=1^roll;memset(f[roll],a[0]=0,sizeof(f[roll]));for(int j=1;j<=n;j++)if(read()) a[++a[0]]=j;for(int s=0;s<p[n];s++)if(f[1^roll][s])for(int j=1;j<=a[0];j++)if(!(s&(p[a[j]-1])))f[roll][s|p[a[j]-1]]=(f[roll][s|p[a[j]-1]]+f[1^roll][s])%m;}printf("%d",f[roll][p[n]-1]);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 3632. 【汕头市选2014】舞伴的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。