题意:

有N个人M只猫P只狗

你要求出N个人各领养一只猫一条狗的方案数

注意某些猫-狗不能同时领养,还有些人不能领养特定的猫

解法:

我们知道装压dp是能解决很多的..

我们C(M,N)枚举出N只猫和P只狗dp..然后..

再匹配人和猫,可以发现两者是独立的,只要算一下答案的乘积之和就是..

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
bool pc[15][15];     //people-cat
bool cd[15][15];     //cat-dog
int dp[1<<10];
int dp2[1<<10];
int cat_dog[1<<10];
int main()
{
    //This is the last chance
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m,p;
    for (;scanf("%d%d%d",&n,&m,&p)!=-1;)
    {
        int q;
        scanf("%d",&q);
        int i;
        memset(pc,true,sizeof(pc));
        memset(cd,true,sizeof(cd));
        for (i=0;i<q;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            x--;
            y--;
            if (x>y) swap(x,y);
            if (x<n)
            {
                pc[x][y-n]=false;
            }
            else
            {
                cd[x-n][y-n-m]=false;
            }
        }
        for (i=0;i<(1<<m);i++)
        {
            int j;
            int cnt=0;
            for (j=0;j<m;j++)
            {
                if ((1<<j)&i) cnt++;
            }
            cat_dog[i]=0;
            if (cnt==n)
            {
                memset(dp,0,sizeof(dp));
                dp[0]=1;
                for (j=0;j<(1<<p);j++)
                {
                    int k;
                    int cnt=0;
                    for (k=0;k<p;k++)
                    {
                        if ((1<<k)&j) cnt++;
                    }
                    for (k=0;k<m;k++)
                    {
                        if ((1<<k)&i) cnt--;
                        if (cnt==-1) break;
                    }
                    if (k==m)
                    {
                        cat_dog[i]+=dp[j];
                        continue;
                    }
                    int chosen=k;
                    for (k=0;k<p;k++)
                    {
                        if ((1<<k)&j) continue;
                        if (cd[chosen][k])
                        {
                            dp[j^(1<<k)]+=dp[j];
                        }
                    }
                }
            }
            //printf("%d\n",cat_dog[i]);
        }
        long long ans=0;
        memset(dp2,0,sizeof(dp2));
        dp2[0]=1;
        for (i=0;i<(1<<m);i++)
        {
            int j;
            int cnt=0;
            for (j=0;j<m;j++)
            {
                if (i&(1<<j)) cnt++;
            }
            if (cnt==n)
            {
                ans+=(long long)dp2[i]*cat_dog[i];
            }
            if (cnt>n) continue;
            for (j=0;j<m;j++)
            {
                if (i&(1<<j)) continue;
                if (pc[cnt][j])
                {
                    dp2[i^(1<<j)]+=dp2[i];
                }
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}