team2012-F3-sol-0002

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
题意：长度为n的全排列，其中给定几个位置的约束(不能放某个数)，求合法方案数。
解法：用容斥原理，全部方案数n! - 违反一个约束的方案数 + 违反两个约束的方案数 - ... 
其中违反k个约束的方案数即 (从m个约束中选出k个互不影响的约束) * (n-k)!
前面一项可用dfs搜出，复杂度2^m
另外出数据的时候貌似有重复的约束-_-#判一下重复就好了
}}}
{{{
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

typedef long long LL;

const int MOD = 55566677;
LL ans, f[60];
int has[60], n, m, rep[60][60];
vector<int> fbd[60];

void dfs(int dp, int cnt)
{
    if(dp == n+1)
    {
        if(cnt&1)
        {
            ans -= f[n-cnt];
            if(ans < 0)
                ans += MOD;
        }
        else
        {
            ans += f[n-cnt];
            ans %= MOD;
        }
        return;
    }
    dfs(dp+1, cnt);
    for(int i=0;i<fbd[dp].size();i++)
    {
        int v = fbd[dp][i];
        if(!has[v])
        {
            has[v] = 1;
            dfs(dp+1, cnt+1);
            has[v] = 0;
        }
    }

}

int main()
{
    f[0] = 1;
    for(int i=1;i<=50;i++)
        f[i] = (f[i-1]*i) % MOD;
    while(cin>>n>>m)
    {
        memset(rep, 0, sizeof(rep));
        for(int i=1;i<=n;i++)
            fbd[i].clear();
        for(int i=1;i<=m;i++)
        {
            int a, b;
            cin>>a>>b;
            if(!rep[a][b])
                fbd[a].push_back(b);
            rep[a][b] = 1;
        }
        ans = 0;
        memset(has, 0, sizeof(has));
        dfs(1, 0);
        cout<<ans<<endl;
    }
    return 0;
}
}}}

题意：长度为n的全排列，其中给定几个位置的约束(不能放某个数)，求合法方案数。
解法：用容斥原理，全部方案数n! - 违反一个约束的方案数 + 违反两个约束的方案数 - ... 
其中违反k个约束的方案数即 (从m个约束中选出k个互不影响的约束) * (n-k)!
前面一项可用dfs搜出，复杂度2^m
另外出数据的时候貌似有重复的约束-_-#判一下重复就好了

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long LL;
const int MOD = 55566677;
LL ans, f[60];
int has[60], n, m, rep[60][60];
vector<int> fbd[60];
void dfs(int dp, int cnt)
{
    if(dp == n+1)
    {
        if(cnt&1)
        {
            ans -= f[n-cnt];
            if(ans < 0)
                ans += MOD;
        }
        else
        {
            ans += f[n-cnt];
            ans %= MOD;
        }
        return;
    }
    dfs(dp+1, cnt);
    for(int i=0;i<fbd[dp].size();i++)
    {
        int v = fbd[dp][i];
        if(!has[v])
        {
            has[v] = 1;
            dfs(dp+1, cnt+1);
            has[v] = 0;
        }
    }
}
int main()
{
    f[0] = 1;
    for(int i=1;i<=50;i++)
        f[i] = (f[i-1]*i) % MOD;
    while(cin>>n>>m)
    {
        memset(rep, 0, sizeof(rep));
        for(int i=1;i<=n;i++)
            fbd[i].clear();
        for(int i=1;i<=m;i++)
        {
            int a, b;
            cin>>a>>b;
            if(!rep[a][b])
                fbd[a].push_back(b);
            rep[a][b] = 1;
        }
        ans = 0;
        memset(has, 0, sizeof(has));
        dfs(1, 0);
        cout<<ans<<endl;
    }
    return 0;
}