容斥原理

其实这就是一个十分简单的奥数问题嘛，说的简单一点，就是我们直接考虑答案，然后算多了减掉，减多了加上，加多了减去……

比如下图就是一个好的例子：

好，所以容斥讲完了，就是这么简单，减了再加，加了再减，直到加或减的数无意义停止。

下面可以给出一道例题：

题目

雕塑

解题思路：

容斥原理，我们知道如果没有限制，答案为n！，但我们会有限制，一个雕像放在了不能放的地方的情况有m（n-1）！，把他减去，但我们又减多了，如果有两个雕像都放在了不能放的地方，那我们上面的做法就重复减了，所以我们要求两个不同行也不同列的雕像组合的种数x，然后加上x（n-2）！。但我们又加多了，如果有三个雕像都放在了不能放的地方，那我们上面的做法就重复加了，所以我们要求三个不同行也不同列的雕像组合的种数x，然后加上x（n-3）！……以此类推，直到他的答案无意义。

代码如下：

#include<cstdio>
#include<cstring>
using namespace std;
long long ans,s,jc[21],n,m,u[21],v[21],a[21],tot;
bool bz[21],bz2[21];
void dg(long long x,long long y,long long z)
{
    if (x>y) s++;
    else
    {
        for (int i=z+1;i<=m;i++)
            if (!bz[u[i]]&&!bz2[v[i]])
            {
                bz[u[i]]=true;
                bz2[v[i]]=true;
                dg(x+1,y,i);
                bz[u[i]]=false;
                bz2[v[i]]=false;
            }   
    }
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for (int i=1;i<=m;i++)
        scanf("%lld%lld",&u[i],&v[i]);
    jc[0]=1;
    for (int i=1;i<=n;i++)
        jc[i]=jc[i-1]*i;
    ans=jc[n];
    for (int i=1;i<=n;i++)
    {
        s=0;
        memset(bz,0,sizeof(bz));
        memset(bz2,0,sizeof(bz2));
        dg(1,i,0);
        if (i%2==0) ans=ans+s*jc[n-i];
        else ans=ans-s*jc[n-i];
    }
    printf("%lld",ans);
    return 0;
}