UVALive646 Deranged Exams [容斥+排列组合]

372 浏览 0 回复 2019-07-10

Zbr_162

+关注

$D e r a n g e d <mtext> </mtext> E x a m s$

$D e s c r i p t i o n$
$N$ 个位置, 求至少前 $K$ 个数字不在自己位置上的方案数 .

$正解部分$
问题转化为: 求前 $K$ 个数字存在 在自己位置上的数字 的方案数 .

分为 $1, 2, 3... K$ 个数字在自己位置上的方案,

比如现在要求 $i$ 个数字在自己位置上的方案数, 为 $C_{K}^{i} * (N - i)!$ ,
但是这样会使得 $i + 1$ 个数字在自己位置上的方案数多出 $1$ 倍, 于是减去 $C_{K}^{i + 1} * (N - i - 1)!$ ,
此时又没有了 $i + 2$ 个数字在自己位置上的方案数, 于是加上 $C_{K}^{i + 2} * (N - i - 2)!$ ,
以此类推, 奇加偶减容斥即可 .

症结 ↑

做了半天发现做错了题!! 本不该做这道题的…

$实现部分$

#include<cstdio>
#define reg register
typedef long long ll;

int Test_id;
int N;
int K;

ll Jc[25];
ll C[25][25];

void Work(){
        scanf("%d%d%d", &Test_id, &N, &K);
        ll Ans = 0;
        for(reg int i = 1; i <= K; i ++){
                if(i & 1) Ans += C[K][i] * Jc[N-i];
                else Ans -= C[K][i] * Jc[N-i];
        }
        printf("%d %lld\n", Test_id, Jc[N] - Ans);
}

int main(){
        C[0][0] = 1;
        for(reg int i = 1; i <= 24; i ++){
                C[i][0] = 1;
                for(reg int j = 1; j <= i; j ++)
                        C[i][j] = C[i-1][j] + C[i-1][j-1];
        }
        Jc[0] = 1;
        for(reg int i = 1; i <= 24; i ++) Jc[i] = i * Jc[i-1];
        int T;
        scanf("%d", &T);
        while(T --) Work();
        return 0;
}

/* 4 1 4 1 2 7 3 3 10 5 4 17 17 */