P1595 信封问题

· · 题解

关于本题二项式反演的做法

直接问恰好没有信封放对不太好做，那么可以转换一下。

设 f(i) 表示至少有 i 个信封放对。

可以推导得：

f(i)={n\choose i}(n-i)!

接下来套二反，设 g(i) 表示恰好有 i 个信封放对位置。

由二项式反演公式得：

g(k)=\sum_{i=k}^{n}(-1)^{i-k}{{i}\choose {k}}f(i)

将 k=0 （即恰好没有信封放对位置）代入：

g(0)=\sum_{i=0}^{n}(-1)^{i}{{i}\choose {0}}f(i)

将 f(i) 代入得：

g(0)=\sum_{i=0}^{n}(-1)^{i}{{n}\choose {i}}(n-i)!

那么就好做了，预处理阶乘，时间复杂度 O(N) 。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,ans;
int fac[25];
int C(int n,int m)
{
    if(n<m)return 0;
    return fac[n]/fac[m]/fac[n-m];
}
signed main()
{
    scanf("%lld",&n);
    fac[0]=1;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i;
    for(int i=0;i<=n;i++)
    {
        if(i&1)ans-=(C(n,i)*fac[n-i]);
        else ans+=(C(n,i)*fac[n-i]);
    }
    cout<<ans;
 }