组合数+容斥

组合数 容斥

HDU 6143:Killer Names

题意

姓和名由两个长度均为$n$的字符串组成。这些字符串中的字符在$m$个给定字符中选择。但要求姓和名不能出现相同的字符。 问有多少种不同的构成这个姓名的方法。$(1≤n,m≤2000)$
$T$组测试数据 $(T≤10)$

样例

Sample Input
2
3 2
2 3

Sample Output
2
18

分析

我们从$m$个元素中选择$i$个元素 $i≤min(n,m-1)$ 来构成姓,此时选法为 $c[i][m]$我们将组合数预处理出来

LL c[maxn][maxn];
void init()
{
    c[0][0]=1;
    for(int i=1;i<maxn;i++)
    {
        c[i][0]=1;
        for(int j=1;j<maxn;j++)
        {
            c[i][j]=c[i-1][j-1]+c[i-1][j];
            if(c[i][j]>=mod)
                c[i][j]-=mod;//对结果取模。加减法比乘除法快40倍。尽量选择加减。（细节）
        }
    }
}

姓：
每次 $c[i][m]$ 的时候对于姓有 $i^n$ 种排列此时会有重复。因为这时候会出现并没有将这$i$种元素用完的情况。就会与之前已经加过的情况重复。这种时候就应该想到容斥了。
名：
处理方法和姓一样选择的时候是$c[m-i][j]$

我们的总的公式为
$ans = \sum_{1 \le i \le n ,0 \le j\le (m-i)} [\binom{i}{m} f[i] \binom{j}{m-i} f(j)]$

对于f[i]的处理就用到了容斥(先加后减，最开始flag=1，然后flag=-flag,一直循环下去)
$in[i]=i^n$ (预处理)

$f[i]=\sum_{0\le j\le i}flag*c[j][i]*in[j]$

边界之类的要注意，还有取模部分也要小心，不要取漏了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=2000+5;
const LL mod=1e9+7;
LL c[maxn][maxn];
void init()
{
    c[0][0]=1;
    for(int i=1;i<maxn;i++)
    {
        c[i][0]=1;
        for(int j=1;j<maxn;j++)
        {
            c[i][j]=c[i-1][j-1]+c[i-1][j];
            if(c[i][j]>=mod)
                c[i][j]-=mod;
        }
    }
}
LL in[maxn],f[maxn];
void getf(int n,int m)
{
    for(int i=0;i<=m;i++)
    {
        in[i]=1;
        for(int j=1;j<=n;j++)
            (in[i]*=i)%=mod;
    }
    for(int i=1;i<=m;i++)
    {
        int flag=1;
        f[i]=0;
        for(int j=min(i,n);j>=0;j--)
        {
            f[i]+=flag*c[i][j]*in[j]%mod;
            f[i]%=mod;
            flag=-flag;
        }
        if(f[i]<0)
            f[i]+=mod;
    }
}
int main()
{
    init();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        getf(n,m);
        LL ans=0;
        for(int i=1;i<=min(n,m-1);i++)
        {
            for(int j=1;j<=min(n,m-1)&&j+i<=m;j++)
            {
                ans+=(c[m][i]*f[i])%mod*(c[m-i][j]*f[j]%mod)%mod;//取模取到位
                if(ans>=mod)
                    ans-=mod;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}