zcmimi's blog
avatar
zc
2019-12-21 19:47:00
  • 本文总阅读量
查看原题

点击跳转

这个显然是错排问题

A_ii在位置i上的所有排列

ans=|\overline A_1\bigcap \overline A_2 \bigcap ...\bigcap \overline A_n|

=|N|

-(|A_1|+|A_2|+...+|A_n|)

+(|A_1\bigcap A_2|+...+|A_{n-1}\bigcap A_n|)

-\ ...

+ (-1)^n |A_1\bigcap A_2\bigcap ... \bigcap A_n

=n!- {n\choose 1}\cdot (n-1)! + {n\choose 2}\cdot (n-2)! - ...\ + (-1)^n {n\choose n}

=n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n\frac{1}{n!}) = D_n

#include<cstdio>
using namespace std;
#define ll long long
#define Fur(i,x,y) for(int i(x);i<=y;++i)
#define N 100011
int n;
ll f[22],c[22][22];
int main(){
    Fur(i,0,20){
        c[i][0]=1;
        Fur(j,1,i)c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    f[0]=1;
    Fur(i,1,20)f[i]=f[i-1]*i;
    while(~scanf("%d",&n)){
        ll ans=f[n];
        int k=-1;
        Fur(i,1,n){
            ans+=c[n][i]*f[n-i]*k;
            k=-k;
        }
        printf("%lld\n",ans);
    }
}
HDU 1465 不容易系列之一
comment评论
Search
search